Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling

Abstract

We consider (uniform) sparsest cut, optimal linear arrangement and the precedence constrained scheduling problem 1 |prec| Sigmaw <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> -So far, these three notorious NP-hard problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme (PTAS), unless NP-complete pmblems can be solved in randomized subexponential time. Furthermore, we prove that the scheduling problem is as-hard to approximate as vertex cover when the so-called fixed cost, that is present in all feasible solutions, is subtracted from the objective function.