Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

Filter by
Sorted by
Tagged with
67
votes
7answers
7k views

Are runtime bounds in P decidable? (answer: no)

The question asked is whether the following question is decidable: Problem  Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect ...
24
votes
3answers
2k views

Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
12
votes
1answer
495 views

Smoothed analysis of approximation algorithms

Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for ...
32
votes
1answer
2k views

Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables. For a constant 0<s<1, Gap-3SATs is the following promise problem: Gap-3SATs ...
27
votes
4answers
1k views

Compendium of the Best Approximation and Hardness Results for NP optimization problems

Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result? Based on the feedback, it seems that it is safe to assume there is not such a ...
32
votes
4answers
846 views

Hardness of approximation assuming NP != coNP

Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am ...
22
votes
2answers
1k views

Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
36
votes
4answers
3k views

Hardness of approximation without the PCP theorem

An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any ...
10
votes
0answers
346 views

Gap hardness of Multi-Dimensional Cover

Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
8
votes
1answer
664 views

Is MAX CUT approximation resistant?

CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since a random ...
16
votes
1answer
412 views

smallest circuit size using XOR gates

Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables. The goal is to compute the minimum ...
9
votes
2answers
1k views

Maximizing sum edge weights

I am wondering if the following problem has a name, or any results related to it. Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,...
9
votes
1answer
843 views

Inapproximability of set cover: can I assume m=poly(n)?

I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem ...
0
votes
2answers
2k views

Is the current best approximation ratio for Vertex Cover problem also a lower bound?

In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we ...
16
votes
0answers
428 views

Is graph coloring complete for poly-APX?

Is the graph coloring problem complete for poly-APX under C-reductions (alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
3
votes
1answer
429 views

What is a “level-r pseudo expectation functional”?

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
3
votes
2answers
133 views

Minimum relevant variables in linear system - additive approximation

In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$ A x = b $$ and the goal is to find a solution $x$ with as few nonzero variables as ...
1
vote
1answer
545 views

The Goemans-Williamson algorithm in the $SOS$ framework

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...