[Colloquium] Talk today (4/15--3:00) Jochen Konemann

[Meridel Trimble]

--------------------------------------------------------------------------------
-------- 

TOYOTA TECHNOLOGICAL INSTITUTE 
--------------------------------------------------------------------------------
-------- 

Date: Tuesday, April 15th, 2003

Time: 3:00 p.m.

Place: Ryerson Hall 251 

Speaker: Jochen Konemann
Carnegie Mellon University

http://www.andrew.cmu.edu/~jochen/

Title: Primal-dual meets local search: Approximating degree-bounded subgraph 
problems

Abstract: 
The main focus of my thesis research is the development of new techniques for 
approximation algorithms for a class of degree-constrained subgraph problems. 
This class of NP-hard problems arises as a natural generalization of classical 
optimization problems such as the widely studied Minimum-cost spanning tree and 
Steiner tree problems. In my talk I will concentrate on my most recent work (to 
appear at STOC 2003): 
We present a new bicriteria approximation algorithm for the degree-bounded 
minimum-cost spanning tree problem: 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. 
Our previous algorithm [K. and Ravi STOC'02] with similar guarantees worked 
only in the case of uniform degree bounds (i.e. $B_v=B$ for all vertices $v$). 
While the new algorithm is based on ideas from Lagrangean relaxation as is our 
previous work, it does not rely on computing a solution to a linear program. 
Instead it uses a repeated application of Kruskal's MST algorithm interleaved 
with a combinatorial update of approximate Lagrangean node-multipliers 
maintained by the algorithm. These updates cause subsequent repetitions of the 
spanning tree algorithm to run for longer and longer times, leading to overall 
progress and a proof of the performance guarantee. 
*Refreshments will be served after the talk in Ryerson 255* 

If you wish to meet with the speaker, please send e-mail to Meridel Trimble 
mtrimble at uchicago.edu