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

136 questions
Filter by
Sorted by
Tagged with
119 views

### Metric TSP with integer edge cost

Given a metric TSP with integer edge cost upper-bounded by a constant $C_{\max}$, can we find an poly-time algorithm solving this TSP instance?
81 views

### What is the complexity of a special multigraph edge coloring problem

Given a multigraph such that there are 0 or 2 edges connecting every two vertices, we are to color the edges of this graph so that adjacent edges receive distinct colors. It is known that we need at ...
24 views

### Approximabilty of submodular over modular maximization

Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
130 views

### Approximation of integral of gaussian function over a parallelepiped

Remark: I posted this question in math stackexchange here and computer science stackexchange https://cs.stackexchange.com/ few weeks ago but obtain no answer. Given a multi-dimensional gaussian ...
32 views

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

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...