Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs

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.

Authors

• Prabhakar Raghavan

Keywords

• Lattices
• Approximation algorithms
• Vectors
• Random variables
• Computer science
• Linear programming
• Design optimization
• Strontium
• Multidimensional systems
• Routing
• Estimation Algorithm
• Probabilistic Method
• Proof Of The Existence
• Lattice Points
• Integer Solution
• Packing Problem
• Conditional Probability
• Total Flow
• Selection Problem
• Non-zero Probability
• Gate Set
• Bernoulli Trials
• Deterministic Time
• Bad Events