Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson · SIAM Journal on Computing · 2011
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.