# 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.

**2**

**1**answer

### Subdividing a sequence such that sum is somewhat equally distributed

**1**

**0**answers

### Algorithmic combinatorial discrete problem (randomized lazy update?)

**2**

**2**answers

### Transforming an optimization problem to maxmin formulation

**0**

**0**answers

### Maximize sum of supermodular functions over nested sets

**1**

**0**answers

### Adaptive Simpsons Quadrature Algorithm for Double Integrals? [closed]

**0**

**3**answers

### Im looking for an algorithm that can solve or approximate the solution to a problem

**1**

**0**answers

### Hutchinson-type algorithm for efficient computation of trace of inverse of non symmetric matrix

**4**

**1**answer

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

**1**

**0**answers

### What's the name of functions that produces a non deterministic solution without losing the exact solution?

**5**

**1**answer

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

**1**

**0**answers

### How to compress variables in a linear regression

**2**

**0**answers

### Can one optimize the probability that an identity is satisfied until the probability is $1$?

**4**

**1**answer

### complexity of bounded knapsack with spoilage

**6**

**1**answer

### Approximate homology of a large simplicial complex

**3**

**3**answers

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

**7**

**1**answer

### Counting spanning trees of a planar graph

**2**

**1**answer

### The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero

**0**

**0**answers

### A name for algorithms that perform well in an asymptotic sense, when inputs are random

**2**

**2**answers

### Fast Algorithms for sum of independent random variables

**1**

**1**answer

### Removing the minimum number of edges to make a graph triangle-free (using set cover)

**5**

**1**answer

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

**1**

**2**answers

### A variation of longest paths in directed acyclic graph

**1**

**0**answers

### Heuristics for this “subset” traveling salesman problem

**2**

**0**answers

### Is there an algorithm for numerical approximation of (naive) period integrals

**1**

**0**answers

### Can Carlsons's iterative algorithm for $\arctan x$ be inverted to get one for $\tan x$?

**3**

**1**answer

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

**10**

**3**answers

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

**6**

**0**answers

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

**1**

**1**answer

### Are there any solvers to Chance Constrained Programming Problems

**3**

**1**answer

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

**1**

**0**answers

### 3-Approximation Algorithm for Weighted 3-Hitting Set (Weighted Set Cover)

**3**

**1**answer

### computational complexity: do we gain acceleration?

**2**

**1**answer

### 3-Approximation Algorithm for 3-Hitting Set

**2**

**0**answers

### Inverse set cover problem

**1**

**1**answer

### 2-approximation algorithm for Minimum Maximal Matching (MMM) problem

**1**

**1**answer

### Approximating a function with sums of gaussians

**0**

**1**answer

### Finding a subgraph of cliques with the minimum total sum weight

**2**

**1**answer

### Complementary slackness for approximately optimal Dual solution

**6**

**1**answer

### Algorithm to compute Matrix Sign Rank?

**2**

**0**answers

### Relationship between weight of spanning tree in a tree metric approximation and the original metric

**2**

**2**answers

### Need a graph theory problem with nontrivial faster approximation algorithm

**0**

**2**answers

### Relaxed path decomposition of a graph

**8**

**1**answer

### Polynomial approximations of curves

**2**

**1**answer

### Bounds on the positive roots of a bivariate polynomial

**2**

**2**answers

### How can I efficiently approximate the stationary distribution of an infinite CTMC with a sparse rate matrix?

**1**

**0**answers

### Asymptotic determinant of $2\times 2$ Toeplitz matrix

**1**

**0**answers

### Matrix Completion: Clearing Step

**18**

**2**answers

### “Fractally self-similar” numbers

**10**

**1**answer

### Confusion with practically implementing rational approximations

**1**

**0**answers