On the hardness of approximating multicut and sparsest-cut

被引：35

作者：

Chawla, S ^{[1
]}

Krauthgamer, R ^{[1
]}

Kumar, R ^{[1
]}

Rabani, Y ^{[1
]}

Sivakumar, D ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA

来源：

TWENTIETH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2005年

关键词：

D O I：

10.1109/CCC.2005.20

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 [STOC, 2002]. A quantitatively stronger version ofthe conjecture implies inapproximability factor of Omega (log log n).

引用

页码：144 / 153

页数：10

共 29 条

[1]

Agarwal A., 2005, P 37 ANN ACM S THEOR, P573

[2]

[Anonymous], THESIS U CHICAGO

[3]

[Anonymous], P 36 ANN ACM S THEOR

[4] Proof verification and the hardness of approximation problems [J].

Arora, S ;

Lund, C ;

Motwani, R ;

Sudan, M ;

Szegedy, M .

JOURNAL OF THE ACM, 1998, 45 (03) :501-555

[5] Probabilistic checking of proofs: A new characterization of NP [J].

Arora, S ;

Safra, S .

JOURNAL OF THE ACM, 1998, 45 (01) :70-122

[6]

ARORA S, 2005, P 37 ANN ACM S THEOR

[7] An O(log k) approximate min-cut max-flow theorem and approximation algorithm [J].

Aumann, Y ;

Rabani, Y .

SIAM JOURNAL ON COMPUTING, 1998, 27 (01) :291-301

[8] Correlation clustering [J].

Bansal, N ;

Blum, A ;

Chawla, S .

MACHINE LEARNING, 2004, 56 (1-3) :89-113

[9] Free bits, PCPs, and nonapproximability - Towards tight results [J].

Bellare, M ;

Goldreich, O ;

Sudan, M .

SIAM JOURNAL ON COMPUTING, 1998, 27 (03) :804-915

[10]

BEN-OR M., 1990, RANDOMNESS COMPUTATI, P91

← 1 2 3 →