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.

learn more… | top users | synonyms

3
votes
1answer
57 views

Computing the (non-convex) boundary of a set of paths between two points

I have a set of paths between two fixed points (marked in red below). Each of these paths consists of an ordered series of $\{x, y\}$ points (marked in blue). I am trying to find the ordered set of ...
1
vote
1answer
99 views

What is the algorithm that matlab used in its built-in function 'pca'?

Do anyone know what is the algorithm that MATLAB used in its built-in function "pca"? I have the following data set: 148.9820 55.8438 210.2150 149.3030 56.8891 208.4280 151.4400 ...
0
votes
0answers
12 views

Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not. Which software would you suggest for rigid transformations? Thank you
2
votes
0answers
45 views

Algorithm for optimizing graph interconnectivity

I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for ...
0
votes
1answer
137 views

Effect of Initial guess B (approximate Hessian) on BFGS algorithm

I am trying to implement BFGS. The purpose is to approximate Hessian matrix only (not using the quasi-newton optimization steps), so i am using steepest ascent for optimization. What I observe is that ...
8
votes
1answer
155 views

Efficient Gravitational Field Implementation

I asked a similar question on physics.stackexchange, being ignorant about this website. I am basically looking for an efficient way to implement gravitational fields. I have a huge 2D space, with ...
4
votes
1answer
98 views

Updating an approximate solution to a linear system in response to a small change

This question was original posted on SO but it was suggested that I post it here. I'm working on a program in which I have a banded matrix M and a vector b, and I want to maintain an approximate ...
1
vote
0answers
124 views

closed form approximation of matrix inverse with special properties

I'm trying to find some theory to help me explicitly express the inverse of a matrix (or a close approximation of the inverse). My matrix has the following properties: invertible positive definite ...
2
votes
1answer
87 views

What is the more than 3rd order Taylor series approximation for a multi-variate function?

Suppose $f$ is a infinite continuously differentiable map: $R^n\to R$, and $x,x_0 \in R^n$, then we have the following second order Taylor expansion of $f(x)$ at $x_0$: $$f(x)\approx ...
0
votes
0answers
82 views

Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
0
votes
1answer
235 views

Successive over-relaxation not converging (when not done in-place)

I'm trying to find the potential given some boundary conditions using the successive over-relaxation method. I have 2 solutions: -One iterates over all elements and applies the formula ...
10
votes
1answer
216 views

Numerical methods for inverting integral transforms?

I'm trying to numerically invert the following integral transform: $$F(y) = \int_{0}^{\infty} y\exp{\left[-\frac{1}{2}(y^2 + x^2)\right]} I_0\left(xy\right)f(x)\;\mathrm{d}x$$ So for a given $F(y)$ ...
3
votes
2answers
574 views

Fast algorithm for Polar Decomposition

As it known, according to the Polar Decomposition, square matrix can be expressed in the next form $$M=QR$$ ($Q$ - othogonal matrix R - positive-semidefinite Hermitian matrix) I need to find this ...
1
vote
1answer
60 views

Determine low-order polynomial lower bound

I have a function $f$ I'd like to determine numerically and I have a bunch of $(x, y)$ pairs which approximate the function in the following sense: all of the points satisfy $f(x) \leq y$, most of the ...
1
vote
1answer
94 views

Assigning Groups Based on Preference List [closed]

I am trying to make a system that will sort a list individuals and their preferred list of others. This may not make complete sense, but bear with me. I have a list of people, each with their list of ...
1
vote
0answers
79 views

Good approximate solutions for a MILP problem

The company I work for has been developing an application for real-time control of sewer networks. Every 5 minutes, a MILP problem is built or updated, then solved using Gurobi. For mid-sized cities, ...
6
votes
1answer
187 views

Computing $\sin(\pi/2)$ numerically

I'm trying to understand the types of numerical errors, to do this I want to calculate $\sin(\pi/2)=1$ numerically. To do this I use the Taylor series of $\sin(x)$ in 0: ...
4
votes
1answer
218 views

Bin-packing: Maximise number of bins / “Fukubukuro” problem?

I recently encountered a problem that looks like a variation of bin packing or knapsack problem, but with the objective to maximise the number of bins/knapsacks: Consider there is a list of M items ...
1
vote
2answers
63 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 ...
7
votes
1answer
314 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 ...
7
votes
3answers
377 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
138 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
120 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
214 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
180 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 ...
10
votes
5answers
410 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 ...
15
votes
1answer
754 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
314 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: ...
11
votes
1answer
1k 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
110 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 ...
12
votes
4answers
535 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 ...
8
votes
1answer
1k 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 ...