We consider (Uniform) Sparsest Cut, Optimal Linear Arrangement and the precedence constrained scheduling problem 1\left| {prec} \right|\sum {w_j C_j }. So far, these three notorious NPhard problems have resisted all attempts to prove inapproximability results. We show that they have no Polynomial Time Approximation Scheme (PTAS), unless NP-complete problems 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.