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 ...
- 27.1k
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,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-...
- 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 ...
- 810
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,801
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 ...
- 18.1k
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,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 ...
- 5,320
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,143
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 $...
- 18.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 $...
- 7,565
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,465
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 ...
- 631
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,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-...
- 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 ...
- 11.5k
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,761
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,700
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 ...
- 4,367
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,...
- 11.6k
3
votes
Graph coloring/partitioning problem
Your problem is NP-complete.
Take an instance $G'=(V',E')$ of the (NP-complete) max-cut problem. Let $m=|E'|$.
Create two new vertices $x_1$ and $x_2$, create the edge between $x_1$ and $x_2$, and ...
- 5,772
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 ...
- 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 ...
- 1,419
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 ...
- 50.8k
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 ...
- 1,703
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) ...
- 306
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 ...
- 9,595
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.
- 2,351
2
votes
Accepted
Approximation algorithms for the maximum $2$-independence set problem
An $O(\sqrt n)$-approximation greedy algorithm for this problem is presented in the paper "Independent sets with domination constraints" by Magnús M. Halldórsson, Jan Kratochvı́l, Jan Arne Tellec (...
- 371
2
votes
Graph coloring/partitioning problem
As the previous answer states, your problem is NP-hard by reduction from Max-Cut. It actually also turns out to be Poly-APX-hard by reduction from Max Independent Set (which is Poly-APX-complete). The ...
- 2,758
Only top scored, non community-wiki answers of a minimum length are eligible