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 ...
- 26.4k
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'|$. ...
- 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-...
- 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 ...
- 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, ...
- 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-...
- 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 $|\...
- 18k
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]...
- 1,781
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 ...
- 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 ...
- 18k
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)$ ...
- 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 ...
- 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 ...
- 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$ ...
- 9,556
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 ...
- 3,094
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.
- 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{...
- 2,101
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 $...
- 18k
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 $...
- 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 ...
- 4,400
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. ...
- 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 ...
- 611
4
votes
Approximating #P-hard problems
Here is a reference to Bordewich, Freedman, Lovász, and Welsh that develops this topic to some extent.
- 5,386
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 ...
- 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-...
- 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 ...
- 11.3k
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/
- 5,424
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 ...
- 1,670
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 ...
- 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,...
- 10.4k
Only top scored, non community-wiki answers of a minimum length are eligible