Probabilistic construction of deterministic algorithms: Approximating packing integer programs
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 24 (02725428) , 10-18
- https://doi.org/10.1109/sfcs.1986.45
Abstract
We consider the problem of approximating an integer program by first solving its relaxation linear program and "rounding" the resulting solution. For several packing problems, we prove probabilistically that there exists an integer solution close to the optimum of the relaxation solution. We then develop a methodology for converting such a probabilistic existence proof to a deterministic approximation algorithm. The methodology mimics the existence proof in a very strong sense.Keywords
This publication has 13 references indexed in Scilit:
- Six Standard Deviations SufficeTransactions of the American Mathematical Society, 1985
- Provably good routing in graphs: regular arraysPublished by Association for Computing Machinery (ACM) ,1985
- A decomposition algorithm for circuit routingPublished by Springer Nature ,1985
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- Global wire routing in two-dimensional arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- “Integer-making” theoremsDiscrete Applied Mathematics, 1981
- Balancing families of setsJournal of Combinatorial Theory, Series A, 1978
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952