18 votes
Accepted

smallest circuit size using XOR gates

This is NP-hard. See: Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7 The ...
user avatar
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'|$. ...
user avatar
  • 3,844
13 votes

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

On the positive side, it is decidable whether a one-tape Turing machine runs in time $n \mapsto C \cdot n + D$ for given $C, D \in \mathbb{N}$, see: David Gajser: Verifying whether One-Tape Non-...
user avatar
  • 26.6k
12 votes
Accepted

Approximating #P-hard problems

We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$. Here are some ...
user avatar
  • 2,743
12 votes
Accepted

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

The answer for (1) is "unlikely". It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha<\frac{3}{2}$, unless $P=NP$. That said, ...
user avatar
  • 9,378
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-...
user avatar
  • 5,712
10 votes
Accepted

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

Let me see if I can clarify this, on a high level. Assume the UG instance is a bipartite graph $G = (V \cup W, E)$, bijections $\{\pi_e\}_{e \in E}$, where $\pi_e\colon \Sigma \to \Sigma$, and $|\...
user avatar
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]...
user avatar
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 ...
user avatar
  • 780
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 ...
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)$ ...
user avatar
  • 3,844
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 ...
user avatar
  • 5,055
7 votes

The Goemans-Williamson algorithm in the $SOS$ framework

Looking at the Goemans–Williamson algorithm in the SOS framework yields no technical advantages: it is exactly the same algorithm and the same ideas are used in the analysis. The only advantages in ...
user avatar
  • 3,721
6 votes
Accepted

Set cover in which some pairs of sets are forbidden

This problem is way harder than set cover. Here is why... Intuitively, you can encode independent set as a problem of this type. Indeed, you are given an instance of independent set - a graph $G$ ...
user avatar
6 votes
Accepted

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

This problem generalizes dominating set: given an unweighted graph, there exists a set of k centers such that all other vertices are at distance 1 from them if and only if there exists a dominating ...
user avatar
6 votes

Complexity of linear programming

See the paper "A parallel approximation algorithm for positive linear programming." by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.
user avatar
  • 3,458
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{...
user avatar
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 $...
user avatar
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 $...
user avatar
  • 7,052
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 ...
user avatar
4 votes
Accepted

Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

Section 1 of the paper, in which the first definition appears, is introductory. The formal development starts at Section 2. The part of the paper starting at Section 2 is completely self-contained. ...
user avatar
  • 14.1k
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 ...
user avatar
4 votes

Approximating #P-hard problems

Here is a reference to Bordewich, Freedman, Lovász, and Welsh that develops this topic to some extent.
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 ...
user avatar
  • 5,712
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-...
user avatar
  • 1,624
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 ...
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/
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 ...
user avatar
3 votes
Accepted

What is a "level-r pseudo expectation functional"?

The degree $r$ pseudo-expectation operator operates on polynomials of at most degree $r$. Since the pseudo-expectation operator is positive semidefinite, we're guaranteed that the square of a ...
user avatar
  • 2,295
3 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,...
user avatar
  • 10.4k

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