Name
Title | ||
|---|---|---|
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\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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/FOCS.2007.40 | Providence, RI |
Keywords | DocType | ISSN |
graph theory,optimisation,polynomial approximation,np-hard pmblems,fixed cost,optimal linear arrangement,polynomial time approximation scheme,precedence constrained scheduling,randomized subexponential time,sparsest cut,vertex cover | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-0-7695-3010-9 | 45 | 1.70 |
References | Authors | |
24 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Monaldo Mastrolilli | 2 | 514 | 39.27 |
| Ola Svensson | 3 | 349 | 36.31 |