Hardness of approximation, aka inapproximability.

learn more… | top users | synonyms

-3
votes
0answers
19 views

multiobjective optimization is easier with fewer objectives, right?

i guess that optimization on nonconvex problems can usually reach better results when there's fewer criteria in the objective function. for example, in a given amount of search time, ten equally ...
3
votes
1answer
86 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 ...
-4
votes
0answers
33 views

hardness of approximating $|V| + OCT$

I try to establish a hardness result for the (strange) objective function "|V|+OCT", where OCT is an odd cycle transversal. I can cleary get that there is no PTAS, but I would like to improve this. ...
2
votes
0answers
59 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
1answer
111 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, ...
7
votes
1answer
344 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
27 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
80 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
vote
1answer
118 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 ...
3
votes
1answer
42 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 ...
8
votes
1answer
186 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 ...
0
votes
0answers
49 views

Minimum vector sets span spaces cover problem

Instance: a set of vectors $V=\{\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n\}$ and $m$ vector sets $V_1,V_2,...,V_m$, each of which contains multiple vectors ($V_i$ may not be a subset of $V$). In our ...
4
votes
1answer
117 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 ...
1
vote
0answers
43 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 ...
14
votes
0answers
302 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
46 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 ...
8
votes
2answers
179 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
166 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 ...
0
votes
0answers
127 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 ...
2
votes
1answer
121 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
127 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
32 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
349 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 ...
7
votes
2answers
312 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 ...
2
votes
2answers
160 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
62 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
176 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: ...
10
votes
1answer
199 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 ...
3
votes
2answers
230 views

Variants of Densest Subgraph Problems

Given a graph $G$, and a vertex-induced subgraph $H$ of $G$, there are two superficially-similar definitions ways to define the density of $H$: (1) Average degree of vertices in $H$ (2) What I will ...
14
votes
2answers
263 views

Approximation in subexponental time

There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete ...
2
votes
0answers
42 views

Approximating BLEDP on restricted graph classes

In the edge-disjoint paths (EDP) problem, we are given an undirected graph $G$, and a set $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$ of $k$ source-sink pairs. The objective is to maximize the number of ...
3
votes
1answer
89 views

Approximation algorithms for multicut for special classes of graphs

The multicut problem is the following. Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of ...
2
votes
0answers
120 views

The non-metric k-median problem

It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic ...
10
votes
2answers
422 views

Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs

I heard of a result in approximate graph coloring, but cannot find the source. The result is: For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph ...
2
votes
2answers
275 views

Multi prover, verifier games and PCP theorem

This question came up while I was going through Siu On Chan's paper on Approximation Resistance. My question is not really related to the paper though. I also guess that this is more of a reference ...
6
votes
1answer
216 views

Complexity of finding large grid minors

What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version ...
7
votes
4answers
799 views

Hardest problems to approximate

Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon >0$. Are there any other problems that are known to be equally hard to approximate? ...
1
vote
1answer
113 views

number of PCP queries

we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?
12
votes
1answer
302 views

Smoothed analysis of approximation algorithms

Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for ...
6
votes
4answers
662 views

How to start studying topics Hardness of approximation and PCP's

Recently I have done an introductory course on complexity theory ( which covered 90% of sipser text book). Now I would like to study the topics Hardness of approximation and PCP's. Can you please ...
9
votes
1answer
236 views

Hitting sets with a subfamily

Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects. A family $H$ of $k$-element subsets of $U$, with $1 \le k < d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ ...
5
votes
0answers
115 views

Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\\{1,\ldots,m\\}$, I want to maximize the quantity \begin{equation} ...
7
votes
0answers
213 views

Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?

In Section 3.2 of On Syntactic versus Computational Views on Approximability by Khanna, et al., the authors state that an adaptation of the results from Proof Verification and Hardness of ...
12
votes
4answers
739 views

hardness of approximating the chromatic number in graphs with bounded degree

I am looking for hardness results on vertex coloring of graphs with bounded degree. Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
4
votes
0answers
131 views

Hardness of approximating |V|+(size of vertex cover)

I know that UGC implies a hardness of 2 for vertex cover, but is there a way to have this hardness on instances where the size of the vertex cover is at least $(1-\epsilon)\frac{|V|}2$? More generally ...
6
votes
2answers
249 views

Inappoximability status of Max One in Three SAT for satisfiable instances

What is the inapproximability status of Max-One-in-Three SAT for satisfiable instances?
33
votes
4answers
3k views

Hardness of approximation without the PCP theorem

An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any ...
3
votes
2answers
184 views

What is the best-known inapproximability result for MIN-3CNF-DELETION?

I am really curious what the best-known inapproximability result is for MIN-3CNF-DELETION. To clarify, this is the problem of minimizing the number of unsatisfied clauses in a CNF SAT formula with at ...
10
votes
2answers
209 views

Approximability of the genus problem

What is currently known about the approximability of the genus problem? A preliminary search tells me that a constant factor approximation is trivial for sufficiently dense graphs, and an ...
-5
votes
1answer
282 views

Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?