Capital Area Theory Seminar

Most optimization problems on an undirected graph reduce in complexity when restricted to instances on a tree. A recent result by Bartal for probabilistically approximating graph metrics by trees shows the following. There is a probability distribution on a space of the spanning trees of the graph such that no edge stretches (in an expected sense) by more than a factor of O(log n log log n). This has resulted in approximation algorithms for several problems which exploit the ease of solving problems on trees. The tree construction of Bartal is inherently randomized and a natural question to ask is whether approximation algorithms which use this construction can be derandomized.

We obtain the following result. We show that any finite metric of size n can be probabilistically approximated by O(n log n) trees such that the distortion of any edge is at most a factor of O(log n log log n). Further the trees and the associated probability distribution can be constructed efficiently in polynomial time. The implications of the result are twofold. First, the construction gives alternative proofs of the constructions of Bartal. Second, the polynomial size of the space we are sampling from enables us to derandomize any approximation algorithm based on the above construction. We obtain the first deterministic approximation algorithms for several problems including group Steiner trees, k-median, buy-at-bulk network design, minimum communication spanning trees, and vehicle routing.

This is based on joint work with Chandra Chekuri, Ashish Goel and Sudipto Guha and Serge Plotkin.

Contact: Vincenzo Liberatore (liberato@umiacs.umd.edu)