# Tag Info

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'|$. ...
• 3,899
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-...
• 5,772
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 ...
• 840
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]...
• 1,811

### 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 ...
• 18.2k

### 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)$ ...
• 3,899

### 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 ...
• 5,460

• 2,153

### 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 ...
• 6,470

### 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,...
• 12.1k