# Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

171 questions
Filter by
Sorted by
Tagged with
618 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 ...
335 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 ...
84 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 ...
170 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 ...
363 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 ...
467 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 ...
413 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 ...
294 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 ...
1k 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? I'...
238 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 ?
499 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 ...
747 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 ...
295 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$ ...
138 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 \sum_{k=...
321 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 ...
2k 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 ...
158 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 ...
324 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?
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 ...
310 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 ...
256 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 $n^\epsilon$-...
593 views

### Is 3SAT problem APX-hard or not?

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

### What is meant by “if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP”?

For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal. A proof is presented on page 39 (Theorem 2.4) in Williamson and Shmoys, The Design of ...
771 views

### What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?

There are many inapproximability results which rely on the unique games conjecture. For example, Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a ...
218 views

331 views

### Hardness of additive approximation to Graph Coloring problem.

In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the ...
255 views

### Explain 0-extension algorithm

I'm trying to implement an approximation algorithm for the 0-extension problem I found the following paper: Approximation Algorithms for the 0-extension problem by Gruia Calinescu, Howard ...
A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$. The problem to find a minimum hitting ...
### Existence of $opt^c$-approximation of Dominating Set with $c < 1$?
Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. ...