Title: Approximation Algorithms for Min-Max Resource Sharing Problems and Its Application in Multicast Congestion Problem
Presentation Slides

In this talk we present approximation algorithms based on a Lagrangian decomposition method via a logarithmic potential reduction to solve min-max resource sharing (MMRS) problems. The goal is to minimize a scalar, which upper-bounds M nonnegative convex constraints. In our algorithms, a block solver is called as an oracle once per iteration. For any relative error tolerance ε ∈ (0,1), we show that a c(1+ε)-approximate solution to the MMRS problem can be delivered by our algorithms in at most O(M(ln M+ε^-2 ln ε^-1)) iterations, given a c(1+O(ε))-approximate block solver. Here the approximation ratio c of the weak block solver can be constant, logarithmic or even worse. This is the first bound independent of the data and the approximation ratio c. For small c the bound is further improved to O(M(ln M+ε^-2)).
As an application we study the problem of minimizing the maximum edge congestion in multicast communication networks. An integer linear program is formulated with exponentially large number of variables. We show that the block problem is the classical Steiner tree problem that can be solved only approximately. Furthermore, our approximation algorithms run in a way similar to the column generation technique such that the hardness due to the large size of the linear program relaxation is avoided.
This is joint work with Klaus Jansen.