# Questions tagged [approximation-algorithms]

An approximation algorithm is an algorithm that finds an approximate solution to a (typically NP-hard) problem. The quality of the algorithm is measured by how close to the actual optimum it performs. For example, it is a constant factor approximation algorithm if it always outputs a solution that is within a constant factor of the optimum. Hardness of approximation is one way to separate NP-hard problems.

**18**

**2**answers

### “Fractally self-similar” numbers

**10**

**3**answers

### Approximate volume computation and lattice point enumeration - hardness

**10**

**1**answer

### Confusion with practically implementing rational approximations

**9**

**1**answer

### State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

**8**

**6**answers

### How to approximate a solution to a matrix equation? [closed]

**8**

**1**answer

### Polynomial approximations of curves

**8**

**1**answer

### How to evaluate binomial coefficients efficiently and as correctly as possible?

**7**

**1**answer

### Counting spanning trees of a planar graph

**7**

**1**answer

### Norms of B-spline coefficients

**7**

**0**answers

### Quantum Optimization as approximating $\mathbb{CP}^{2^n -1}$ with the orbits of a subgroup of SU($2^n$)

**6**

**3**answers

### Approximating e with 2s and 3s

**6**

**3**answers

### Approximating derivatives between gridpoints

**6**

**1**answer

### Approximate homology of a large simplicial complex

**6**

**1**answer

### Algorithm to compute Matrix Sign Rank?

**6**

**2**answers

### Approximating the action of the U(N) exponential map

**6**

**0**answers

### Any approximation algorithms for self-avoiding walks?

**5**

**2**answers

### Getting started: combinatorial optimization for computer scientists

**5**

**2**answers

### Runge-Kutta method with c<1

**5**

**1**answer

### Lovász $\delta$ condition for LLL Algorithm

**5**

**1**answer

### Hypergraph Chromatic Number vs Degree, Clique-Size

**5**

**1**answer

### Searching for an inhomogeneous diophantine approximation algorithm

**5**

**3**answers

### How to make an approximation of path with polynom P(x,y)=0?

**5**

**1**answer

### Row-based iterative algorithms for computing the kernel of a matrix

**5**

**1**answer

### What is the LP gap of vertex cover in planar graphs?

**5**

**0**answers

### Approximating a max-cut's intersection with other cuts

**5**

**0**answers

### envelope function for a linear combination of gaussian distributions

**4**

**4**answers

### When we use Bernstein polynomials in application

**4**

**2**answers

### Set Cover:Greedy vs LP

**4**

**2**answers

### Can you solve this problem using a finite number of queries?

**4**

**3**answers

### Construct the best piece-wise linear continuous function fitting given curve

**4**

**1**answer

### Fast Bourgain embedding (or similar embeddings)?

**4**

**1**answer

### complexity of bounded knapsack with spoilage

**4**

**2**answers

### Estimate size of graph by taking random walks

**4**

**1**answer

### Practical error-estimates for (adaptive) Newton-Cotes Quadrature

**4**

**0**answers

### Disjoint paths in temporal graphs

**3**

**2**answers

### Sparse approximation of the inverse of a sparse matrix

**3**

**2**answers

### How to check numerical precision of my computation of Stieltjes-constants?

**3**

**2**answers

### Approximation of curves

**3**

**3**answers

### iteratively (approximately) solving a sum of exponentials

**3**

**1**answer

### Using Fourier Transform to speed up calculation of forces following an inverse square law

**3**

**3**answers

### Detecting slow growth in a finite number of queries

**3**

**3**answers

### Approximation of half-integers modified Bessel function of the second kind

**3**

**1**answer

### Approximating John's ellipsoid from uniform sampling of a centrally symmetric convex polyhedron

**3**

**1**answer

### Is there a Fourier Analytic way to approximate volume?

**3**

**1**answer

### computational complexity: do we gain acceleration?

**3**

**0**answers

### Do higher-order splines with Lipschitz derivatives exist on finite sets?

**3**

**0**answers

### Group Travel Salesman Problem

**3**

**0**answers

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

**3**

**0**answers

### Solving a Certain Constrained Isoperimetric Approximation-Problem

**3**

**0**answers