Scaling of Linear Programs
Abstract
The scaling technique has been used often in designing efficient algorithms for combinatorial optimization problems. This thesis unifies problem-specific scaling approaches into a linear programming framework. Solution of linear programs by scaling involves successive solutions of what we call the timing problem. This tuning problem arises when one transforms a solution for the previous scale into a solution for the next scale. It is shown that the tuning problem has a nice format under certain assumptions, and it is precisely this convenience which has led to fast scaling algorithms for many combinatorial problems. The author also examines schemes that use a relaxation of complementary slackness, and shows that one such scheme is equivalent to scaling. He proposes a generalization of an approximation algorithm by Gabow and Tarjan and discusses its application to the tuning problem. Finally, he discusses scaling of the shortest path problem and the weighted matching problem in this linear programming framework.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1988
- Accession Number
- ADA197548
Entities
People
- Milind A. Sohoni
Organizations
- University of Illinois Urbana–Champaign