Tutte seminar - Chaitanya Swamy

Linear-programming based techniques for minimum latency problems

Abstract:

We introduce a problem that is a common generalization of the uncapacitated facility location (UFL) and minimum latency (ML) problems. In our model, as in UFL, there are facilities and clients, and we need to open facilities and assign clients to facilities. But in addition we need to find a tour visiting the facilities that determines the time by which a facility will be activated or replenished. The goal is to minimize the facility-opening costs and the delays incurred by the clients, where the latter term takes into account both the time taken for a client to reach its assigned facility and the time taken to activate this facility. Besides being a natural problem of interest, this problem unifies various diverse combinatorial-optimization problems, and our results yield various insights for some of these problems as well. We give a polylogarithmic approximation algorithm for this problem, which is tight in that any improvement on this would yield an analogous improvement for the group Steiner tree problem, which is long-standing open problem.

Our techniques yield LP-based methods for minimum-latency (and other vehicle routing) problems. Specifically, we obtain two LP-relaxations for ML, which we believe offer a promising source for improving the approximation for ML. We can prove an upper bound on the integrality gap by drawing upon various ideas in scheduling, facility location and polyhedral theory. 

This talk will be self contained.