Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
In this talk we present results from our recent STOC'03 paper on minimum-cost degree-bounded spanning trees: Given an undirected graph with nonnegative edge weights and degree bounds $B_v>1$ for all vertices $v$, find a spanning tree $T$ of minimum total edge-cost such that the maximum degree of each node $v$ in $T$ is at most $B_v$. Our algorithm finds a tree in which the degree of each node $v$ is $O(B_v+\log n)$ and the total edge-cost is at most a constant times the cost of any tree that obeys all degree constraints. The new algorithm achieves similar guarantees as our previous result from STOC'00. The new algorithm is direct in the sense that it does not need to solve an LP to compute the approximate solution. The algorithm demonstrates the use of a novel hybri between primal-dual and local-search algorithms. We will also outline how the above can be extended to approximate minimum-cost degree-bounded Steiner trees. A result which is to appear at FSTTCS '03.

This is joint work with R. Ravi at CMU.