Approximability of maximum splitting of k-sets and some other Apx-complete problems

被引：21

作者：

Kann, V ^{[1
]}

Lagergren, J ^{[1
]}

Panconesi, A ^{[1
]}

机构：

[1] FREE UNIV BERLIN, FACHBEREICH INFORMAT, D-14195 BERLIN, GERMANY

来源：

关键词：

approximation; algorithms; combinatorial problems; computational complexity;

D O I：

10.1016/0020-0190(96)00046-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：105 / 110

页数：6

共 15 条

[1]

Alimonti P, 1995, LECT NOTES COMPUT SC, V1017, P167

ALIZADEH, F .

[3]

Alon N., 1991, The Probabilistic Method

[4]

Bellare M, 1995, AN S FDN CO, P422, DOI 10.1109/SFCS.1995.492573

[5]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[6]

Crescenzi P, 1995, LECT NOTES COMPUT SC, V959, P539, DOI 10.1007/BFb0030875

[7]

Goemans M. X., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P422, DOI 10.1145/195058.195216

[8]

GOEMANS MX, 1996, IN PRESS J ACM

[9] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS [J].

JOHNSON, DS .

[10]

Karger D., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P2, DOI 10.1109/SFCS.1994.365710