Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut

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. Copyright © by SIAM.


Published in:
SIAM Journal on Computing, 40, 2, 567-596
Year:
2011
Publisher:
Society for Industrial and Applied Mathematics
ISSN:
1095-7111
Laboratories:




 Record created 2015-08-28, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)