# Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

156 questions
Filter by
Sorted by
Tagged with
68 views

### How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...
44 views

### Sherali-Adams lowerbound instance of Unique Games constructed via CLT

The question comes from the following paper I have been reading: [1] Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev. Theorem 6.1 ...
86 views

### How hard is it to determine ex(n,G)?

Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known ...
65 views

### Example of a hardness-of-approximation proof which improves the approximation factor?

Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so ...
20 views

68 views

109 views

### hardness of constant approximation of largest matching set

We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more. Given a graph $G=(V,E)$ a subset $U\subseteq V$...
167 views

### Approximating the Radius of a (Dense) Graph

For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius. A $(1+\epsilon)$-approximating of APSP for a ...
58 views

### Studying the hardness of polynomial-time approximability using the concept of stability of approximation

In the Conclusion section, the author of this paper "Stability of Approximation Algorithms for Hard Optimization Problems" by Juraj Hromkovič, 1999 claims that Using the notion of stability one can ...
219 views

### Looking for approximation class between NPO and Exp-APX

I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) ...
1k 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 ...
58 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 ...
132 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 ...
100 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 ...
158 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://...
389 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 ...
141 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 ...
96 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 ...
53 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 ...
256 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). ...
183 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 ...
92 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$...
60 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 ...
185 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 ...
866 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 ...
242 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 ...
### 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 ...
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 ...