Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

Filter by
Sorted by
Tagged with
76 votes
9 answers
11k 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 to input ...
John Sidles's user avatar
  • 1,536
39 votes
9 answers
4k views

Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
Shiva Kintali's user avatar
37 votes
4 answers
4k 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 ...
Andras Farago's user avatar
32 votes
4 answers
887 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 ...
Shiva Kintali's user avatar
32 votes
1 answer
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 ...
Tsuyoshi Ito's user avatar
  • 16.5k
29 votes
4 answers
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 ...
27 votes
3 answers
993 views

When is relaxed counting hard?

Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
Yaroslav Bulatov's user avatar
25 votes
3 answers
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 ...
Simd's user avatar
  • 3,902
24 votes
1 answer
958 views

What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?

There are many inapproximability results which rely on the unique games conjecture. For example, Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a ...
Tsuyoshi Ito's user avatar
  • 16.5k
22 votes
2 answers
2k 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, ...
21 votes
4 answers
979 views

Examples of hardness phase transitions

Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$. One example is counting spin ...
Yaroslav Bulatov's user avatar
17 votes
1 answer
531 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 ...
Mohammad R. Salavatipour's user avatar
17 votes
3 answers
530 views

Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?

There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an ...
Oleksandr Bondarenko's user avatar
16 votes
3 answers
569 views

UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?

Background: In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary ...
Daniel Apon's user avatar
  • 6,011
16 votes
0 answers
490 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 ...
Hermann Gruber's user avatar
15 votes
2 answers
349 views

Approximation in subexponental time

There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete ...
Turbo's user avatar
  • 12.9k
15 votes
1 answer
486 views

Hitting set of pairwise intersecting families

A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$. The problem to find a minimum hitting ...
Yota Otachi's user avatar
  • 1,731
15 votes
1 answer
633 views

Does PSPACE-completeness imply approximation hardness?

It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it? Is this "tight"? (i.e., are there PSPACE-...
R B's user avatar
  • 9,458
13 votes
4 answers
2k views

hardness of approximating the chromatic number in graphs with bounded degree

I am looking for hardness results on vertex coloring of graphs with bounded degree. Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
afshi7n's user avatar
  • 271
13 votes
0 answers
527 views

Approximating and bounding Ramsey numbers

Calculating the diagonal Ramsey numbers R(s,s) is hard. There is a famous quote from Joel Spencer: Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and ...
Artem Kaznatcheev's user avatar
12 votes
2 answers
830 views

Hardness of Vertex Separators

For a given graph $G$, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions $G$ into two disjoint graphs of approximately equal ...
Shiva Kintali's user avatar
12 votes
2 answers
365 views

Hierarchy theorem for approximation ratios?

As is well known, NP-hard optimization problems can have many different approximation ratios, ranging all the way from having a PTAS to not being approximable within any factor. In between, we have ...
Jeremy Hurwitz's user avatar
12 votes
1 answer
566 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 ...
Aaron Schild's user avatar
11 votes
2 answers
257 views

Approximability of the genus problem

What is currently known about the approximability of the genus problem? A preliminary search tells me that a constant factor approximation is trivial for sufficiently dense graphs, and an $n^\epsilon$-...
user avatar
11 votes
2 answers
298 views

Which 2P1R Games are Potentially Sharp?

Two-prover one-round (2P1R) games are an essential tool for hardness of approximation. Specifically, the parallel repetition of two-prover one-round games gives a way to increase the size of a gap in ...
Derrick Stolee's user avatar
11 votes
1 answer
296 views

Almost always almost right

I am looking for a complexity class that relates to APX as BPP relates to P. I have already asked the same question here, but perhaps TCS would be a more fruitful location for answers. The reason for ...
Michael's user avatar
  • 323
11 votes
0 answers
239 views

Inapproximability of multiterminal cut

In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
someone's user avatar
  • 1,424
10 votes
2 answers
501 views

Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs

I heard of a result in approximate graph coloring, but cannot find the source. The result is: For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph ...
Jeremy Kun's user avatar
  • 1,318
10 votes
3 answers
763 views

When is the duality gap of semidefinite programming (SDP) zero?

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold? For example, when one goes back and forth ...
gradstudent's user avatar
  • 1,453
10 votes
1 answer
947 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 ...
Edith Elkind's user avatar
10 votes
2 answers
470 views

Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. ...
Bart Jansen's user avatar
  • 5,275
10 votes
1 answer
617 views

Is the following graph optimization problem approximable within a constant factor?

Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
maxdan94's user avatar
  • 563
10 votes
2 answers
492 views

Consequences of lower bounds for $\epsilon$-nets on approximation

Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
James King's user avatar
  • 2,633
10 votes
1 answer
490 views

Hardness of approximating fractional chromatic number on bounded degree graphs

Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
Ashwinkumar B V's user avatar
10 votes
2 answers
2k 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,...
Aaron Roth's user avatar
  • 9,900
10 votes
0 answers
363 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 ...
Tsuyoshi Ito's user avatar
  • 16.5k
9 votes
2 answers
568 views

Approximating #P-hard problems

Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there ...
user0928's user avatar
  • 165
9 votes
2 answers
3k views

What are good approximation algorithms for the subset sum problem so far?

By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
sma's user avatar
  • 467
9 votes
1 answer
735 views

Is Max-Cut APX-complete on triangle-free graphs?

In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph such that the number of edges between S and the complement of S is as large as possible. Max-Cut is APX-...
Standa Zivny's user avatar
9 votes
2 answers
988 views

Quantum PCP and hardness of simulating of Hamiltonians

I have a few questions about Quantum PCP conjecture: What is the statement of the quantum PCP conjecture? What implications would Quantum PCP theorem have for simulating of Hamiltonians? Is it ...
user avatar
9 votes
4 answers
1k views

Planted Clique in G(n,p), varying p

In the planted clique problem, one must recover a $k$-clique planted in an Erdos-Renyi random graph $G(n,p)$. This has mostly been looked at for $p=\frac{1}{2}$, in which case it is known to be ...
sd234's user avatar
  • 575
9 votes
1 answer
480 views

A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence ...
Jeremy Kun's user avatar
  • 1,318
9 votes
1 answer
313 views

Hitting sets with a subfamily

Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects. A family $H$ of $k$-element subsets of $U$, with $1 \le k < d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ ...
user avatar
9 votes
0 answers
251 views

Which version of KAKUTANI does lie in PPAD?

The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite ...
Daniil Musatov's user avatar
8 votes
4 answers
410 views

In-approximability results in severely restricted graph classes

Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in ...
Mohammad Al-Turkistany's user avatar
8 votes
1 answer
800 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 ...
Mohammad Al-Turkistany's user avatar
8 votes
1 answer
540 views

Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
cs_student_273's user avatar
8 votes
1 answer
427 views

Approximating Random MAX-k-SAT

It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity. Should ...
Lior Eldar's user avatar
  • 1,224
8 votes
2 answers
767 views

Approximation Algorithms for MAXSAT

Trying to find the optimal solution to WEIGHTED-MAX-3SAT, the weighted version of the 3-SAT optimization problem, is NP-hard. In fact, even approximating the non-weighted version of MAX-SAT ...
Huck Bennett's user avatar
  • 4,878
8 votes
1 answer
276 views

Request for references on multicommodity flow-cut results

This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to ...
user7823's user avatar
  • 453

1
2 3 4 5