14 votes
Accepted

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

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. ...
Yury's user avatar
  • 3,899
11 votes
Accepted

Does Max Planar 3-SAT admit a PTAS?

Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach. This has been observed, for instance, in Theorem 17 in Pierluigi Crescenzi and LucaTrevisan: "Max NP-...
Gamow's user avatar
  • 5,772
10 votes
Accepted

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

Cormen, Leiserson, Rivest and Stein say that this algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of another algorithm achieving better. Vertex Cover is NP-hard to ...
PsySp's user avatar
  • 840
10 votes
Accepted

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

There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition. This is due to Ramana. (For another take on this involving SOS, see [KS12]...
Ryan O'Donnell's user avatar
9 votes

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

For the SDP in standard form $$ \min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\}, $$ Slater's condition reduces to the existence of a positive ...
Sasho Nikolov's user avatar
8 votes

What are the hardness results known for CSP over $\mathbb{F}_q$?

Here is a summary of what is known about approximability of $k$-CSP over a domain of size $q$: The best known approximation algorithms for the problem give an $\Omega(q \max(k, \log q)/q^k)$ ...
Yury's user avatar
  • 3,899
8 votes

Why does Dinur's proof of the PCP theorem fail to work for unique games?

The powering step fails. After the powering, each vertex is labeled with a neighborhood of the original graph. each edge checks that its endpoints agree on the intersection of their neighborhoods, and ...
Or Meir's user avatar
  • 5,460
5 votes

Distinguising between the cases of low or high cover number

Proving hardness of this sort of gap problem is usually how hardness of approximation is proved. For vertex cover, Håstad's famous paper (Theorem 7.1.) showed what you are asking for with $a=3/4$ and $...
Sasho Nikolov's user avatar
5 votes

Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

Here is the proof of Petrank's reduction. This was suggested to me by Édouard Bonnet. I still do not know whether this can be turned into an L-reduction. Suppose there is a PTAS algorithm $\mathscr{...
Florent Foucaud's user avatar
5 votes

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018): Given a context-free grammar of size $s$ generating a finite language $L$, it is impossible to ...
Hermann Gruber's user avatar
4 votes

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

If $\ell$ and $k$ are fixed, there are only finitely many possible problem instances, so you can write a program that has a hardcoded table of all possible instances and their solutions. Consequently,...
D.W.'s user avatar
  • 12.1k
4 votes
Accepted

Maximizing a monotone supermodular function s.t. cardinality

I think this is an example showing no kind of approximation is possible except with exponential$(k)$ value queries. Let $f(S) = 0$ if $|S| \leq k$, otherwise $f(S) = |S| - k$. Now pick a special set $...
usul's user avatar
  • 7,615
4 votes

Is there any research on approximation of reals with computable numbers

It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and ...
Bjørn Kjos-Hanssen's user avatar
4 votes

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

The problem was also solved in my article "The intensional content of Rice's Theorem" POPL'2008, where I prove that no "complexity clique" is decidable. A complexity clique is a class of programs ...
Andrea Asperti's user avatar
4 votes
Accepted

Minimum relevant variables in linear system - additive approximation

Unless $P=NP$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $\text{OPT}+d$. Suppose otherwise, and consider some fixed $d$ for which there ...
Gamow's user avatar
  • 5,772
4 votes
Accepted

Maximum Positive Negative Set Cover Problem

This problem has a few simple constant-factor approximation algorithms, such as the trivial algorithm that picks the $C' \in \{\emptyset, C\}$ with a higher objective score. Here's a loose constant-...
Yonatan N's user avatar
  • 1,642
4 votes
Accepted

Optimization problems with same optimal value, but different approximation behavior

What about something like minimum vertex cover vs. minimum fractional vertex cover (i.e., optimal solution of the LP relaxation of the vertex cover problem) in bipartite graphs? These two problems ...
Jukka Suomela's user avatar
4 votes

Where to find info on (polytime) approximability of various discrete optimization problems?

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/
Hermann Gruber's user avatar
4 votes
Accepted

Best approximations of Minimum Dominating Sets in chordal graphs

The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the Set Cover problem ...
Christian Komusiewicz's user avatar
4 votes

3 Matroid Intersection, a Special Case

Your problem is a multi-budgeted matroid intersection with two budgets. There is a PTAS for that [1]. However, your case is so special, better algorithm exists. You can assume there is only a single ...
Chao Xu's user avatar
  • 4,479
3 votes

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

In 2016–2018, in a series of papers, Dinur, Khot, Kindler, Minzer and Safra show that Vertex Cover is NP-hard to approximate to any factor better than $\sqrt{2}$, thus improving Dinur and Safra's ...
Yuval Filmus's user avatar
  • 14.5k
3 votes
Accepted

Given oracle for Max-3SAT compute clauses that cannot be satisfied

Given an instance of 3SAT with $m$ clauses, you can find the set of clauses that are not satisfied in some optimal assignment with $O(m)$ calls to the oracle. The algorithm: Call the oracle on the ...
Tom Tseng's user avatar
  • 164
3 votes
Accepted

Proving hardness of approximation with reduction in terms of 1/$\epsilon$

You can think of $\epsilon$ as parametrizing a family of reductions to a family of approximation problems: The $\epsilon$-th problem is to compute a $1+\epsilon$ approximation to the underlying ...
Andrew Morgan's user avatar
3 votes
Accepted

the shorstest cycle containing two given points

The problem of finding the shortest simple cycle through two vertices in a weighted undirected graph can be solved in the same time as Dijkstra's algorithm for a single shortest path, by applying ...
David Eppstein's user avatar
3 votes
Accepted

Hardness of approximating acyclic chromatic number

It is not a gap-preserving reduction, but an approximation factor preserving reduction. The comment by Manuel Lafond is very close to an answer (but I cannot concur with the opinion that having same ...
Cyriac Antony's user avatar
3 votes
Accepted

Approximation algorithm for balanced bipartite independent set?

There is a nice reduction by Chalermsook et al. (WG 2020) that can give the kind of approximation you want. I'll describe it below in terms of finding balanced complete bipartite subgraph (biclique) ...
Pasin Manurangsi's user avatar
3 votes
Accepted

Hardness of Maximum Independent Set in 3-Colorable Graphs

As detailed below, the problem of finding an independent set of size $\Omega(n^{1-\delta})$ in 3-colorable graphs is essentially equivalent to $O(n^\delta)$-approximating 3-COLOR. Currently, the best ...
Neal Young's user avatar
  • 10.8k
2 votes

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

Worst case you have a Kolmogorov complexity issue where you have chosen half of the $k^l$ words at random. Since it is random your CFG has to take $O(k^l)$ space since it cannot compress.
Chad Brewbaker's user avatar
2 votes

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

To add to the previous answers, this problem is not only undecidable but $Σ^0_2$ complete. Thus, it is undecidable even if the decider has an oracle for the halting problem. To clarify the ...
Dmytro Taranovsky's user avatar
2 votes

Is Asymptotic PTAS $\subseteq$ APX?

I think one issue is that we need to fix the "scale" of the problem. For example, the paper I refer to below defines NPO so that the objective function takes only positive integer values. With that ...
Sasho Nikolov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible