Journal
SIAM JOURNAL ON COMPUTING
Volume 40, Issue 2, Pages 567-596Publisher
SIAM PUBLICATIONS
DOI: 10.1137/080729256
Keywords
hardness of approximation; graph theory
Funding
- Nuffield Foundation [NAL32608]
- Swiss National Science Foundation [200021-104017/1, 200020-122110/1]
- ERC [226203]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available