Approximation algorithms for logistic network design
(Thesis proposal for Ph.D. in Algorithms, Combinatorics and Optimization)

Amitabh Sinha, PhD student in ACO at GSIA, Carnegie Mellon University, under Prof. Ravi

Abstract:

The field of logistic network design deals with the design of networks for the manufacture, storage and transshipment of goods to sinks where they are consumed. The field is of fundamental importance for many applications, from corporations engaged in marketing consumer goods to military units shipping out for operations in a distant theater. Therefore, it has received a lot of attention since the beginnings of the field of operations research. This thesis proposes to study the design of logistic networks from the perspective of approximation algorithms.

We present approximation algorithms for some simple versions of typical problems which arise in logistic network design. For example, one might require to extend the classical uncapacitated facility location model with the requirement that a network with sufficient capacity is installed to route traffic between open facilities and clients. We obtain a constant-factor approximation for this problem. In general, we study the applicability of two major techniques - combinatorial lower bounds and linear programming. We then propose to study the usefulness of these techniques for some more problems which are currently open, or develop new techniques for these problems.

The full proposal is available at http://www.andrew.cmu.edu/~asinha/proposal.ps