Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Primal-dual algorithms come of age: Approximating MST's with nonuniform degree bounds
Speaker:Jochen Könemann
coming from:CMU Pittsburgh
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 29 July 2003
Time:13:30
Duration:45 Minutes
Location:Saarbrücken
Building:46.1 - MPII
Room:024
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 hybrid
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.

This is joint work with R. Ravi at CMU.

Contact
Name(s):Martin Skutella
Phone:116
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):