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

**7**

**0**answers

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

**6**

**0**answers

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

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

**0**answers

### Disjoint paths in temporal graphs

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

### Estimating the growth rate of nondeterministic finite automata

**3**

**0**answers

### Tiling a rectangle with weighted cells (min-max problem)

**3**

**0**answers

### Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

**3**

**0**answers

### A.G. Vitushkin's “Easily representable families of functions” - can it be generalized?

**3**

**0**answers

### Place n telescopes on a sphere in R^d to see the whole sky

**3**

**0**answers

### Algorithm for testing satisfiable fraction of linear equations mod 2

**2**

**0**answers

### How to solve a QCQP where constraints are balls?

**2**

**0**answers

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

**2**

**0**answers

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

**2**

**0**answers

### Inverse set cover problem

**2**

**0**answers

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

**1**

**0**answers

### Computational complexity of rate $\frac{1}{2}$ codes

**1**

**0**answers

### Why does Y. Moshe Vardi use this specific matrix when estimating source-destination traffic intensities with EM algorithm?

**1**

**0**answers

### what is the computational complexity of Louvain algorithm?

**1**

**0**answers

### Minimum delay path in time-dependent graph

**1**

**0**answers

### Meaning of L-reduction from Dominating set problem

**1**

**0**answers

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

**1**

**0**answers

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

**1**

**0**answers

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

**1**

**0**answers

### How to compress variables in a linear regression

**1**

**0**answers

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

**1**

**0**answers

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

**1**

**0**answers

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

**1**

**0**answers

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

**1**

**0**answers

### Matrix Completion: Clearing Step

**1**

**0**answers

### FPTAS for approximating the permanent of a matrix

**1**

**0**answers

### Optimize a convex hull on a 2D histogram so the selected points match a target shape

**1**

**0**answers

### An MST-like problem with vertex selection

**1**

**0**answers

### Multiobjective semidefinite programming

**1**

**0**answers

### Representing vertices of a cube using linear combination of tensor product of smaller cubes

**0**

**0**answers

### Norm of vector components optimization of linear matrix combination

**0**

**0**answers

### How to derive space bound for Morris(a) approximate counting algorithm

**0**

**0**answers

### A variant of travel salesman problem with charging points

**0**

**0**answers

### A variant of Steiner tree problem

**0**

**0**answers

### Maximize sum of supermodular functions over nested sets

**0**

**0**answers

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

**0**

**0**answers

### Approximation for accumulative set cover

**0**

**0**answers

### Pure greedy algorithm

**0**

**0**answers

### sparsest cut always has solution

**0**

**0**answers

### Approximate a piecewise linear path by a path with bounded curvature

**0**

**1**answer