Fast approximation algorithms for fractional packing and covering problems
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 495-504
- https://doi.org/10.1109/sfcs.1991.185411
Abstract
Fast algorithms that find approximate solutions for a general class of problems, which are called fractional packing and covering problems, are presented. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. The algorithms are based on a Lagrangian relaxation technique, and an important result is a theoretical analysis of the running time of a Lagrangian relaxation based algorithm. Several applications of the algorithms are presented.Keywords
This publication has 15 references indexed in Scilit:
- Fast approximation algorithms for multicommodity flow problemsPublished by Association for Computing Machinery (ACM) ,1991
- The maximum concurrent flow problemJournal of the ACM, 1990
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990
- Speeding-up linear programming using fast matrix multiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- A new algorithm for minimizing convex functions over convex setsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsJournal of Computer and System Sciences, 1988
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear ProgrammingJournal of the ACM, 1978
- Fast approximation algorithms for knapsack problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- A Linear Programming Approach to the Cutting Stock Problem—Part IIOperations Research, 1963