Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
Authors:
- Christoph AmbühlCAChristoph Ambühl
- Monaldo MastrolilliMMMonaldo Mastrolilli
- Ola SvenssonOSOla Svensson
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (2) , 567-596
Abstract
We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme, unless NP-complete problems can be solved in randomized subexponential time. Furthermore, we show that the same techniques can be used for the Maximum Edge Biclique problem, for which we obtain a hardness factor similar to previous results but under a more standard assumption.Keywords
This publication has 24 references indexed in Scilit:
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cutACM Transactions on Algorithms, 2008
- An improved approximation ratio for the minimum linear arrangement problemInformation Processing Letters, 2007
- ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUTcomputational complexity, 2006
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite CliqueSIAM Journal on Computing, 2006
- A survey of graph layout problemsACM Computing Surveys, 2002
- On Bipartite and Multipartite Clique ProblemsJournal of Algorithms, 2001
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- On the complexity of approximating the independent set problemInformation and Computation, 1992