Loading...
research article
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.
Type
research article
Authors
Publication date
2011
Published in
Volume
40
Issue
2
Start page
567
End page
596
Peer reviewed
NON-REVIEWED
EPFL units
Available on Infoscience
August 28, 2015
Use this identifier to reference this record