Name
Title | ||
|---|---|---|
Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1137/080729256 | SIAM J. Comput. |
Keywords | Field | DocType |
minimum linear arrangement problem,polynomial time approximation scheme,hardness factor,randomized subexponential time,maximum edge biclique problem,inapproximability result,inapproximability results,np-complete problem,notorious np-hard graph problem,sparsest cut problem,previous result,hardness of approximation,computer science,graph theory | Graph theory,Discrete mathematics,Complete bipartite graph,Graph,Combinatorics,Hardness of approximation,Mathematics,Polynomial-time approximation scheme,Maximum cut | Journal |
Volume | Issue | ISSN |
40 | 2 | 0097-5397 |
Citations | PageRank | References |
35 | 1.27 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Monaldo Mastrolilli | 2 | 514 | 39.27 |
| Ola Svensson | 3 | 349 | 36.31 |