Questions tagged [approximation-hardness]
Hardness of approximation, aka inapproximability.
174
questions
0
votes
2answers
2k views
Is the current best approximation ratio for Vertex Cover problem also a lower bound?
In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we ...
2
votes
0answers
59 views
General hardness results for convex problems
What are the hardness results that we know of for generally convex problems? In particular, I know of the result that every convex problem is in $P$ when we have an oracle for generating a separating ...
3
votes
0answers
143 views
Maximize number of edges covered by an independent set of vertices
Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
4
votes
1answer
105 views
From Lasserre maps to pseudo-distributions
Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is ...
7
votes
1answer
185 views
What are the hardness results known for CSP over $\mathbb{F}_q$?
I found two related papers,
There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf
A kind of a stronger result might be found in these two other papers, http://...
10
votes
3answers
554 views
When is the duality gap of semidefinite programming (SDP) zero?
I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold?
For example, when one goes back and forth ...
-1
votes
1answer
162 views
Given oracle for Max-3SAT compute clauses that cannot be satisfied
We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
-2
votes
1answer
100 views
Proving hardness of approximation with reduction in terms of 1/$\epsilon$
I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 < \epsilon < 1$. The reduction is polynomial in $n$ (the size of the instance of the ...
1
vote
0answers
56 views
About increasing the objective values of certificates for Max-Clique SDP
Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
7
votes
1answer
288 views
Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs
My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3).
...
8
votes
0answers
204 views
NP-hardness of approximation for unconstrained submodular maximization
The problem of unconstrained submodular maximization can be phrased as follows:
Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$.
Here a ...
2
votes
0answers
93 views
About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$...
1
vote
0answers
64 views
About complexity of recovering or learning Bayesian networks
Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
3
votes
2answers
232 views
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
Problem:
Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...
4
votes
1answer
1k views
Maximizing a monotone supermodular function s.t. cardinality
I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this.
Question: Is it known to be true or is there a hardness result ...
5
votes
0answers
243 views
Maximizing the number of selected edges with opposing requirements
Consider the following problem:
Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$.
Output: a subset of vertices $W$ of size $k$ which maximizes the ...
3
votes
1answer
311 views
Approximation algorithms for the maximum $2$-independence set problem
I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct ...
0
votes
0answers
33 views
On approx-preserving P- and A-reducibilities
Let $X$ and $Y$ be two NPO problems.
Let $(f,g)$ be a reduction between $X$ and $Y$,
in particular, assume that $(f,g)$ is both P-reduction and A-reduction,
i.e.,
there exist two poly-time ...
4
votes
2answers
528 views
Graph coloring/partitioning problem
I'm interested in the complexity of the following problem:
Problem $P$: Given an undirected planar graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, ...
16
votes
1answer
434 views
smallest circuit size using XOR gates
Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables.
The goal is to compute the minimum ...
1
vote
0answers
146 views
hardness of approximating clique: how using FGLSS reduction with PCP verifier of hastad
I try to understand the $n^{1-\epsilon}$ hardness of approximating clique for any $\epsilon$ provided in [1]: www.nada.kth.se/~johanh/cliqueinap.ps
In fact, I only want to understand the proof of ...
3
votes
0answers
121 views
Set cover approximation ratio as a function of m (number of sets)
Feige's well known result (and more recent results) show that set cover cannot be approximated within a factor of $(1 - o(1)) \ln n$, where $n$ is the number of variables. What if we want an ...
1
vote
1answer
201 views
Is there any research on approximation of reals with computable numbers
I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
2
votes
0answers
124 views
Hardness of approximately counting independent sets with a PRAS, rather than FPRAS
It is known that approximately counting the independent sets of a graph is hard, even if randomness can be used, and even if we restrict ourselves to bounded degree graphs with degree bound at least 6....
1
vote
1answer
413 views
What are multiple rounds of SOS/Lasserre hierarchy?
Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things?
Or to take a ...
1
vote
1answer
560 views
The Goemans-Williamson algorithm in the $SOS$ framework
If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...
3
votes
1answer
439 views
What is a “level-r pseudo expectation functional”?
In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
5
votes
0answers
241 views
Is MAX-SAT SETH (like) hard?
If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy.
There ...
5
votes
1answer
264 views
Set cover in which some pairs of sets are forbidden
I'm trying to find an approximation algorithm for a variant of the weighted set cover problem. However, this variation doesn't seem to let me apply the traditional set cover arguments for an ...
3
votes
0answers
104 views
$\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ problems
All the problems which are either $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ cannot admit a $\mathsf{PTAS}$, unless $P=NP$. I would like to know whether $\mathsf{MaxSNP}$ ...
3
votes
2answers
223 views
What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?
My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, ...
8
votes
1answer
472 views
Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?
Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
3
votes
0answers
59 views
APx hardness of Multiterminal Cut Problem
In a Multiterminal Cut problem input is a graph G=(V,E) and a set of k terminals T which is a subset of vertex set V. There is a weight w(e) associated with each edge in the graph. The question is to ...
5
votes
0answers
116 views
The distribution on the solution space induced by randomized rounding
Consider the Goemans-Williamson algorithm for the MAX-CUT problem.
It is known, that if $maxcut(G) \geq 1-\epsilon$, then
the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
1
vote
1answer
141 views
Confusion in 2012 paper by Austrin and Håstad regarding hardness of approximating GLST
The paper in question is "On the Usefulness of Predicates", Per Austrin, Johan Håstad (arXiv:1204.5662 [cs.CC]).
On page 13, Example 8.2 they define a predicate $P$ which is $GLST$ with an ...
4
votes
1answer
84 views
Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al
I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075).
The ...
9
votes
1answer
338 views
A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut
I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence ...
4
votes
1answer
237 views
Inapproximability of $(\alpha, \beta)$ bi-criteria approximation
An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$...
1
vote
0answers
46 views
inapproximability of logarithic factor of indepence set [closed]
The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to ...
16
votes
0answers
434 views
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
0
votes
0answers
85 views
How can I show that zero-one programming is not in APX?
How can I show that zero-one programming is not in APX?
Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the
zero-one programming problem to Vertex Cover and show that ...
9
votes
2answers
408 views
Approximating #P-hard problems
Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there ...
2
votes
1answer
222 views
Complexity of linear programming
It is known that Linear Programming (LP) is P-complete.
I am interested in approximation algorithms for LP.
There are numerous inapproximability results for NP optimization problems,
e.g. it is NP-...
0
votes
0answers
224 views
Calculating exact/approximate solution to a formula
Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$.
Consider ...
5
votes
1answer
214 views
Hardness of approximating chromatic number of triangle-free graphs
The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs.
Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?
5
votes
0answers
212 views
Approximate c-chromatic number, each color class is P4-free (cograph)
The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
1
vote
0answers
62 views
Approximation algorithm to a minimization problem with optimization function going to zero
I have a simple function to minimize, but it is not discrete: $f(x) = 2x - \alpha x - c(x)$, where $x$ is a natural number, $\alpha$ is a rational number, $0 \leq \alpha \leq 1$, and $0 \leq c(x) \leq ...
14
votes
1answer
527 views
Does PSPACE-completeness imply approximation hardness?
It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it?
Is this "tight"? (i.e., are there PSPACE-...
9
votes
3answers
903 views
Planted Clique in G(n,p), varying p
In the planted clique problem, one must recover a $k$-clique planted in an Erdos-Renyi random graph $G(n,p)$. This has mostly been looked at for $p=\frac{1}{2}$, in which case it is known to be ...
3
votes
2answers
335 views
Set packing with maximum coverage objective
We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.
Set-Packing asks how many disjoint sets we can pack, and is defined ...
