A method of finding nearly-optimal solutions to a problem. Generally, this terminology is applied to algorithms and heuristics for solving NP-Hard problems in computer science.
1
vote
2answers
54 views
Estimate (non-)drift in noisy data
I have a time series representing the result of a complex calculation (physical simulation). Due to round-off errors and approximation errors, there will be some "noise" on the data series. In some ...
6
votes
1answer
126 views
Polynomial Fitting from Chebyshev Coefficients
I have been reading Numerical recipes about how to create a power series approximation to a function once you have a Chebyshev approximation to the function. However it is still very unclear to me how ...
6
votes
3answers
194 views
Choosing subset of vectors to approximate a subspace
Suppose I have a high-dimensional vector space $X$, a subspace $V \subset X$, and a collection of $n$ vectors $\{x_i\}_{i=1}^n \subset X$.
My question is: How can I choose a small collection $k < ...
3
votes
2answers
119 views
How to prove that my problem is np-hard
For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting.
The problem is that i know that this is hard to solve, but i dont know if ...
2
votes
1answer
103 views
Numerically designing a periodic 1D curve that maximizes an integral area objective and satisfies value, derivative, and frequency constraints
I need to write MATLAB program (or use an existing one) to obtain Fourier series coefficients. Let's say the series is going to approximate a 1D curve. The boundary conditions are:
value of the ...
0
votes
1answer
95 views
Quickly computing inversion of a large sparse partial stochastic matrix
Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
3
votes
1answer
88 views
Integral average approximation and error bounds
I'm looking into integrals of the form:
$$\int_a^b {f(x)g(x)dx}$$
Where $f(x)$ is unknown, but it's integral is:
$$\int_a^b {f(x)dx}=F$$
It's been suggested to me that one could approximate this ...
8
votes
4answers
249 views
Approximate spectrum of a large matrix
I want to compute the spectrum (all the eigenvalues) of a large sparse matrix (hundreds of thousands of rows). This is hard.
I am willing to settle for an approximation. Are there approximation ...
12
votes
1answer
204 views
Drawbacks of Newton-Raphson approximation with approximate numerical derivative
Suppose I have some function $f$ and I want to find $x$ such that $f(x)\approx 0$. I might use the Newton-Raphson method. But this requires that I know the derivative function $f'(x)$. An analytic ...
3
votes
2answers
178 views
How to detect key turning points on a driven road?
I am looking for a description of algorithm which allows me to detect key turning points on the road amongs a set of all given points.
I've ilustrated my problem on the below image:
Green spots: ...
9
votes
1answer
537 views
The Remez Algorithm
The Remez algorithm is a well-known iterative routine to approximate a function by a polynomial in the minimax norm. But, as Nick Trefethen [1] says about it:
Most of these [implementations] go ...
5
votes
1answer
101 views
Using an approximation algorithm to adapt parameter values of a given algorithm
Problem:
I have an incremental online clustering algorithm which need 4 parameters that should be specified by the user before execution. The algorithm will gives "good results" if "a good parameter ...
8
votes
4answers
301 views
Can the solution of a linear system of equations be approximated for only the first few variables?
I have a linear system of equations of size nxn, where n is large. However, the variables that I'm interested in are just the first n variables. Is there a way I can approximate the solution for the ...
7
votes
1answer
383 views
Efficient solution of mixed integer linear programs
Many important problems can be expressed as a mixed integer linear program. Unfortunately computing the optimal solution to this class of problems is NP-Complete. Luckily there are approximation ...
