Probabilistic construction of deterministic algorithms: Approximating packing integer programs

aharoni, 1985, Dual integer linear programs and the relationship between their optima, 476

Angluin, 1979, Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. System Sci., 19, 155, 10.1016/0022-0000(79)90045-X

Beck, 1981, “Integer-making” theorems, Discrete Appi. Math., 3, 1, 10.1016/0166-218X(81)90022-6

Chernoff, 1952, A measure of asymptotic efficiency for tests based on the sum of observations, Ann. Math. Statist., 23, 493, 10.1214/aoms/1177729330

Erdös, 1974

Even, 1976, On the complexity of timetable and multicommodity flow problems, SIAM J. Comput., 5, 691, 10.1137/0205048

Hu, 1985, A decomposition algorithm for circuit routing, Math. Programming Stud., 24, 87, 10.1007/BFb0121044

Karmarkar, 1984, A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373, 10.1007/BF02579150

Karp, 1972, Reducibility among combinatorial problems, 85

Karp, 1983, Global wire routing in two-dimensional arrays, 453

Kramer, 1982, Wire-Routing is NP-Complete

Lovász, 1975, On the ratio of optimal and fractional covers, Discrete Math., 13, 383, 10.1016/0012-365X(75)90058-8

Olson, 1978, Balancing families of sets, J. Combin. Theory Ser. A, 25, 29, 10.1016/0097-3165(78)90028-6

Papadimitriou, 1982

Raghavan, 1985, Provably good routing in graphs: Regular arrays, 79

Raghavan, 1987, Randomized rounding: Provably good algorithms and algorithmic proofs, Combinatorica, 7, 365, 10.1007/BF02579324

Spencer, 1985, Six standard deviations, Trans. Amer. Math. Soc., 289, 679, 10.1090/S0002-9947-1985-0784009-0