# Questions tagged [approximation]

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.

84 questions
Filter by
Sorted by
Tagged with
45 views

278 views

### Does this Algorithm (probably Fourier like) Exist for 2D Shapes? [closed]

Update: Someone changed the title to this post to a possible answer ("Fourier decomposition of parametric shapes") but I changed it to a different title as that makes it clear what I was asking. As I ...
469 views

### Fast algorithm for computing matrix square root using randomized linear algebra?

Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
882 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 ...
70 views

### Fast approximate solver for vehicle routing problem

I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
138 views

Suppose we have a conformal mapping from the unit disk in the $\omega$ plane onto the exterior of a polygon in the $z$ plane. The Schwarz-Christoffel mapping in this case is defined as: $$f(u) = A - ... 1answer 237 views ### Size of jump for piecewise discontinuous approximations If one has a sufficiently smooth function u that is approximated by a piecewise constant function u_h=\Pi^0_h u on a mesh of cell size h (where \Pi^0_h is the L_2 projection onto the ... 2answers 387 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 ... 1answer 368 views ### Matching/Assignment Problem I'm not sure how I can represent and solve the following problem. I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ... 1answer 42 views ### Slightly change two vectors to satisfy a constraint \vec{a}\cdot\vec{b} \approx c \vec{\alpha} \cdot \vec{\beta} = c \vec{\alpha} is close to \vec{a} and \vec{\beta} is close to \vec{b} Given \vec{a}, \vec{b} and c, how to find \vec{\... 0answers 57 views ### Weighted Set Cover in practice, beyond the greedy algorithm According to the wikipedia page for Set Cover, the greedy algorithm for weighted set cover achieves the polynomial-time approximation bound. There are other techniques for solving Set Cover, such as ... 6answers 1k 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 ... 1answer 102 views ### Approximation of a non linear problem with python I need your help to solve a problem I'm working on for school. My goal is to approximate the coefficients of a weight matrix so that they check particular properties. So I have W the weight matrix ... 2answers 243 views ### Image hash similarity matching possible? I have the following question: We have two face image files (JPEG), a Matrix of 128\times 128 with values between 0-255. We would like to hash both image files using a function f(x, key). Where I ... 1answer 78 views ### Which are some good algorithms and heuristics to calculate the similarity between two matrices? Say I have a matrix like this: \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix} And this one: \begin{bmatrix} ... 1answer 98 views ### Taylor expansion of error - Finite elements approximation In some of my computations I calculate a scalar value \lambda_h (in my case an eigenvalue) depending on a finite element discretization of the domain. Usually we can manage to find estimates of the ... 1answer 203 views ### Linear Least-Squares Point-to-Plane ICP degenerative case I'm trying to implement Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration Paper describes linear approximation for point to plane distance for rigid ICP. This approach is ... 1answer 1k views ### Derivatives of a Chebychev polynomial I am using Chebychev collocation nodes for approximation, and my problem requires me to calculate derivatives of the polynomial. I have been reading from a few sources, but I am not sure I understand ... 1answer 53 views ### Chebychev Polynomial derivatives at zero points and extreme points I was looking for some help with derivatives of Chebychev polynomials at zero points. The recursive expression,$$ T_{(j+1)}(x) = 2xT_j(x) - T_{(j-1)}(x) $$has the derivative$$ T'_{j+1}(x) = 2T_j(...
I'm measuring the integral of a quantity which, mathematically, requires the computation of a dilogarithm function. $$\operatorname{Li}_2(be^{ax})$$ where $b$ and $a$ (are real and) can be positive ...