RANDOMIZED ROUNDING - A TECHNIQUE FOR PROVABLY GOOD ALGORITHMS AND ALGORITHMIC PROOFS

被引：608

作者：

RAGHAVAN, P ^{[1
]}

THOMPSON, CD ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY, DIV COMP SCI, BERKELEY, CA 94720 USA

来源：

关键词：

D O I：

10.1007/BF02579324

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：365 / 374

页数：10

共 14 条

[1]

AHARONI R, 1985, 17TH P ACM S THEOR C, P476

[2]

ANGLUIN D, J COMPUTER SYSTEM SC, V19, P155

CHERNOFF, H .

ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04) :493-507

[4]

Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048

[5] MAXIMUM DEGREE AND FRACTIONAL MATCHINGS IN UNIFORM HYPERGRAPHS [J].

FUREDI, Z .

HOEFFDING, W .

ANNALS OF MATHEMATICAL STATISTICS, 1956, 27 (03) :713-721

[7]

HU TC, 1985, MATH PROGRAM STUD, V24, P87, DOI 10.1007/BFb0121044

[8]

Karp R. M., 1983, 24th Annual Symposium on Foundations of Computer Science, P453, DOI 10.1109/SFCS.1983.23

[9]

Karp R. M., 1972, COMPLEXITY COMPUTER, P85

[10] RATIO OF OPTIMAL INTEGRAL AND FRACTIONAL COVERS [J].

LOVASZ, L .