Report Number: CS-TR-92-1419
Institution: Stanford University, Department of Computer Science
Title: Fast approximation algorithms for fractional packing and covering problems
Author: Plotkin, Serge A.
Author: Shmoys, David B.
Author: Tardos, Eva
Date: November 1993
Abstract: This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangean relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running time of a Lagrangean relaxation-based algorithm. We give several applications of our algorithms. The new approach yields several orders of magnitude of improvement over the best previously known running times for the scheduling of unrelated parallel machines in both the preemptive and the non-preemptive models, for the job shop problem, for the cutting-stock problem, and for the minimum cost multicommodity flow problem.
http://i.stanford.edu/pub/cstr/reports/cs/tr/92/1419/CS-TR-92-1419.pdf