Approximation Algorithms for Multicommodity Flow and Shop Scheduling Problems

摘要

In this thesis, we give efficient approximation algorithms for two classicalcombinatorial optimization problems: multicommodity flow problems and shop scheduling problem. The algorithms we develop for these problems yield solutions that are not necessarily optimal, but come with a provable performance guarantee; that is, we can guarantee that the solution found is within a certain percentage of the optimal solution. This type of algorithm is known as an approximation algorithm. Our results show that by allowing a small error in the solution of a problem, it is often possible to gain a significant reduction in the running time of an algorithm for that problem. In Chapter 2, we study the multicommodity flow problem. The multicommodity flow problem involves simultaneously shipping several different commodities from their respective sources to their sinks in a single network so that the total amount of flow going through each edge is no more than its capacity. Associated with each commodity is a demand, which is the amount of that commodity that we wish to ship. Given a multicommodity flow problem, one often wants to know if there is a feasible flow, i.e., if it is possible to find a flow that satisfies the demands and obeys the capacity constraints. More generally, we might wish to know the maximum percentage z such that at least z percent of each demand can be shipped without violating the capacity constraints. The latter problem is known as the concurrent flow problem. multicommodity flow, scheduling, combinatorial optimization, network algorithms, approximation algorithms, randomized algorithms.