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

**0**answers

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

**3**

**1**answer

### complexity of bounded knapsack with spoilage

**5**

**1**answer

### Approximate Homology of a Large Simplicial Complex

**2**

**2**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

**0**

**0**answers

### How to square the (approximate) model count of a cnf formula?

**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**

**0**answers

### 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$?

**-1**

**0**answers

### Truncation error of product and composition of functions?

**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

**0**

**0**answers

### Finding a path crossing minimum number of distinct colors

**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?

**8**

**2**answers

### What is the Time Complexity of the Matrix Exponential?

**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

### Performance guarantee of RLF [closed]

**3**

**0**answers

### Group Travel Salesman Problem

**9**

**1**answer

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

**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

**5**

**0**answers

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

**1**

**0**answers

### FPTAS for approximating the permanent of a matrix

**3**

**0**answers