[A&C seminar] On Designing Approximation Algorithms with Guarantees Independent of the Graph Size
Speaker: Ankur Moitra , MIT
Date: April 27 2009
Time: 4:00PM to 5:10PM
Location: G575
Contact: Aleksander Madry, madry@mit.edu
Relevant URL: http://people.csail.mit.edu/madry/algcompsem/
Leighton and Rao established an approximate min-cut max-flow theorem for uniform multicommodity flows. Linial, London and Rabinovich and Aumann and Rabani solved a major open question and proved that the min-cut max-flow ratio for general maximum concurrent flow problems (when there are $k$ commodities) is $O(\log k)$. Here we attempt to derive a more general theory of Steiner cut and flow problems, and we prove bounds that are poly-logarithmic in $k$ for a much broader class of multicommodity flow and cut problems. Our structural results are motivated by the meta question: Suppose we are given a $poly(\log n)$ approximation algorithm for a flow or cut problem - when can we give a $poly(\log k)$ approximation algorithm for a generalization of this problem to a Steiner cut or flow problem?
Thus we require that these approximation guarantees be independent of the size of the graph, and only depend on the number of commodities (or the number of Steiner nodes in a Steiner cut problem). For many natural applications of multicommodity flows and cuts, we expect that the number of commodities $k$ is much smaller than $n$, and for such problems we get approximation algorithms that have much stronger guarantees.
Our approach fundamentally relies on metric geometry and oblivious routing. We use the structural results we develop to constructively reduce a broad class of Steiner cut and flow problems to a uniform case (on $k$ nodes) at the cost of a loss of a $poly(\log k)$ in the approximation guarantee. We cannot concisely define this class but we can use our results to give $poly(\log k)$ approximation algorithms for a number of problems for which such results were previously unknown, such requirement cut, $l$-multicut, and natural generalizations of oblivious routing, min-cut linear arrangement and minimum linear arrangement.
See other events that are part of
See other events happening in April 2009
