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

We consider (uniform) sparsest cut, optimal linear arrangement and the precedence constrained scheduling problem 1 |prec| Sigmaw j C j -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.