Name
Abstract | ||
|---|---|---|
We show that the Multicut, Sparsest-Cut, and Min-2CNF ≡ Deletion problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot (2002). A quantitatively stronger version of the conjecture implies an inapproximability factor of
\(\Omega(\sqrt{\log \log n}).\) |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s00037-006-0210-9 | conference on computational complexity |
Keywords | DocType | Volume |
hardness of approximation,fourier analysis | Journal | 15 |
Issue | ISSN | ISBN |
2 | 1420-8954 | 0-7695-2364-1 |
Citations | PageRank | References |
112 | 6.23 | 30 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shuchi Chawla | 1 | 1872 | 186.94 |
| Robert Krauthgamer | 2 | 1417 | 103.80 |
| Ravi Kumar | 3 | 13932 | 1642.48 |
| Yuval Rabani | 4 | 2265 | 274.98 |
| D. Sivakumar | 5 | 3515 | 389.02 |