Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique

By Subhash Khot. 45th Annual IEEE Symposium on Foundations of Computer Science, 2004

369 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/3f69ff45fc185abc918953e7b79df8675ceaa08f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Christopher R'e
2. Vitaly Feldman
3. Peter Richtárik
4. Tong Zhang
5. Martin Takác
6. Michael I. Jordan
7. Martin Jaggi
8. Sebastian U. Stich

In Computational Theory and Mathematics

1. Vitaly Feldman
2. Elena Grigorescu
3. Aristides Gionis
4. Francesco Bonchi
5. Jude W. Shavlik
6. Santosh Srinivas Vempala
7. Francesco Gullo
8. Lev Reyzin

Citations in the corpus

• On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation (2015, neutral): “′ − (|E| −E(S′,T′)) | {z } #edges outsideS′ × T′ = 3E(S′,T′)−|S′||T′| −|E|. This problem is a particular variant of the general problem of finding large dense subgraphs in bipartite graphs; see, e.g., [3, 21, 22] and the references therein. If the size of the subgraph is fixed a priori, finding the den”
• Statistical algorithms and a lower bound for detecting planted cliques (2012, background): “This is a variant of the densest k -subgraph problem, which itself is a natural generalization of k -clique that asks to recover the densest k -vertex subgraph of a given n -vertex graph [Feige, 2002, Khot, 2004, Bhaskara et al., 2010, 2012].”
• Truncated power method for sparse eigenvalue problems (2011, background): “In general, however, Khot (2006) showed that DkS has no polynomial time approximation scheme (PTAS), assuming that there are no sub-exponential time algorithms for problems in NP. Mathematically, DkS can be restated as the following binary quadratic programming problem: where W is the (non-negative…”
• Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS (2011, background): “The proof (Appendix B.6) is by reduction to the graph minimum bisection problem [14], which is hard to approximate (unless P = NP , there is no PTAS).”
• Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees (2013, background): “From the perspective of (in)approximability, Khot [22] shows that there cannot exist any PTAS for the DkS problem under a reasonable complexity assumption.”