Questions tagged [approximation-hardness]
Hardness of approximation, aka inapproximability.
171
questions
4
votes
1answer
103 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
177 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
506 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
161 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
99 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
55 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
283 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
198 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
62 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
221 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
301 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
502 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
419 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
144 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
118 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
197 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
123 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
410 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
555 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
431 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
239 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
254 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
222 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
467 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
115 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
139 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
83 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
330 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
234 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
433 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
82 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
396 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
213 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
213 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
196 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
59 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
521 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
890 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
308 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 ...
4
votes
1answer
80 views
Bellman principle and approximability
Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
0
votes
3answers
715 views
Comparing graphs
I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths.
example:
...
11
votes
1answer
259 views
Almost always almost right
I am looking for a complexity class that relates to APX as BPP relates to P. I have already asked the same question here, but perhaps TCS would be a more fruitful location for answers.
The reason for ...
