18
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 reduction is from Vertex Cover and is very nice.
Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+...
14
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'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$.
Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is ...
13
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-Deterministic Turing Machines Run in Time $Cn+D$, arXiv:1312.0496
12
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, Crescenzi et al. have shown that unless the polynomial hierarchy collapses, Bin Packing is not APX-Hard.
As for (2), perhaps you could phrase it as "Does not ...
12
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 basic results for this:
Case 1: $k=2^{n-1}-\mathrm{poly}(n)$
Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\...
11
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-completeness made easy"
Theoretical Computer Science 28, (1999), Pages 65-79
10
One paper that gives an answer to this question is Chalermsook, Laekhanukit, & Nanongkai (2013).
There are also related works in the context of Fixed Parameter Tractability such as
Hajiaghayi, Khandekar, & Kortsarz (2013) and Chitnis, Hajiaghayi, Kortsarz (2013).
These hardness results are proven under various assumptions such as ETH or existence of ...
10
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 $|\Sigma| = m$. You want to construct a new graph $H$ so that if the UG instance is $1-\delta$ satisfiable, then $H$ has a large cut, and if the UG instance is not ...
10
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].) To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me.
One notable consequence of this work is ...
10
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 approximate with a factor better than 1.36:
http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf
Also check the following paper which give ...
9
If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$. (See Bollobás, p.283 and Corollary 11.2.) Changing $p$ should therefore not affect the hardness of planting a clique with $\omega(\log n)$ vertices as long as the clique is too ...
9
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 definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A_i^T X) = b_i$. I would guess this is satisfied for any SDP you can find in the ...
8
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)$ approximation [MM14 and MNT16].
For $k = \Omega(q)$, there is a matching hardness of $O(kq/q^k)$ by Håstad (UGC-hardness) and Chan (NP-hardness) [Chan13].
For $k$ ...
8
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 that this labeling satisfies the edges in this intersection. However, the edge cannot check anything about part of the labeling that lies outside the ...
7
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 doing so are:
Arguably the algorithm seems less "magical" in that viewpoint, though of course that's a matter of taste.
It's a good basic case to get intuition ...
6
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$ with $n$ vertices, and a number $k$, and the question is whether the graph $G$ has an independent set of size $k$.
We assume that $k$ is large (say, polynomial in ...
6
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 set of size k.
Dominating set is hard to approximate with a ratio better than $\ln n$. In the above observation the optimal value for the k-center problem is ...
6
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.
5
One (old but useful) reference along these lines is Woeginger's 1998 paper on the connection between DPs and approximability:
When Does a Dynamic Programming Formulation Guarantee the Existence
of a Fully Polynomial Time Approximation Scheme (FPTAS)?
5
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{A}$ for MAX k VERTEX COVER, thus giving a $(1-\varepsilon)$-factor-approximate solution on a cubic graph $G=(V,E)$ with $|V|=n, |E|=m=3n/2$.
We can use $\...
5
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 $b=7/8$.
4
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 closed w.r.t. programs with similar behavior and complexity. I also provides necessary conditions for semi-decidable properties.
Programs running in O(n^k) are a ...
4
This is meant more as a comment than as a solution, but is a bit too long to fit in the comment box. There is a bit of handwaving and ignoring of small factors, but I can formalize the work below further if requested.
Here's a heuristic reason why (a) might be difficult to approximate within a small factor.
Consider the random-in-random PLANTED DENSE ...
4
Here is a reference to Bordewich, Freedman, Lovász, and Welsh that develops this topic to some extent.
4
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. Therefore, if there is any mismatch between a definition in Section 1 and a definition elsewhere, the latter is the correct one.
In theoretical computer science, ...
4
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 papers. See for instance
Becher, Verónica; Reimann, Jan; Slaman, Theodore A., Irrationality exponent, Hausdorff dimension and effectivization, ZBL06837203.
4
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 $S^*$ uniformly at random from all sets of size $k$, and let $f(S^*) = 0.5$.
I'm claiming that this function is supermodular because every element initially ...
4
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 does exist such an approximation algorithm $A$. We construct a new multiplicative polynomial time approximation algorithm from $A$, that always returns solutions ...
4
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-factor hardness result. No significant effort was put into optimizing the constant. I'm sure others can find something tighter.
Let $G = (V,E)$ be an instance ...
4
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 have the same optimal value.
However, if I give you a black-box algorithm that finds a $(1+\epsilon)$-approximation of the minimum fractional vertex cover, this ...
Only top voted, non community-wiki answers of a minimum length are eligible