期刊
SIAM JOURNAL ON COMPUTING
卷 40, 期 2, 页码 567-596出版社
SIAM PUBLICATIONS
DOI: 10.1137/080729256
关键词
hardness of approximation; graph theory
资金
- Nuffield Foundation [NAL32608]
- Swiss National Science Foundation [200021-104017/1, 200020-122110/1]
- ERC [226203]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据