FAST APPROXIMATION ALGORITHMS FOR FRACTIONAL PACKING AND COVERING PROBLEMS

This paper presents fast algorithms that find approximate solutions fo r a general class of problems, which we call fractional packing and co vering problems. The only previously known algorithms for solving thes e problems are based on general linear programming techniques. The tec hniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously appli ed to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangian relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running t ime of a Lagrangian relaxation-based algorithm We give several applica tions of our algorithms. The new approach yields several orders of mag nitude of improvement over the best previously known running times for algorithms for the scheduling of unrelated parallel machines in both the preemptive and the nonpreemptive models, for the job shop problem, for the Held and Karp bound for the traveling salesman problem, for t he cutting-stock problem, for the network embedding problem, and for t he minimum-cost multicommodity flow problem.