Seminario Interdipartimentale di Algoritmica
 
 
 

Lunedì 2 Aprile 2001  ore 12:00
A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
Prof. R. Ravi
Graduate School of Industrial Administration, Carnegie Mellon University

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

Abstract:
In this talk, we will present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. In this problem, we are given a graph, a nonnegative cost function on the edge, and a positive integer B, and the goal is to find a minimum cost spanning tree with maximum degree at most B. In an n-node graph, our algorithm finds a spanning tree with maximum degree O(B+ log n) and cost O(OPT(B)) where OPT(B) is the minimum cost of any spanning whose maximum degree is at most B. Our algorithm uses ideas from Lagrangean duality in a novel way. We show how a set of optimum Lagrangean multipliers yields bounds on both degree and cost of the computed solution. This talk will describe joint work with Jochen Koenemann, CMU.