Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, December 10, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Rico Zenklusen (IFOR)
Network interdiction studies the maximum impact that the removal of a limited number of edges or vertices can have on a graph optimization problem. Most interdiction problems are NP-hard, and only little is known about their approximability. One of the oldest and most-studied interdiction problems is minimum spanning tree (MST) interdiction. Here, an MST problem is given together with positive edge costs and a budget B. The goal is to remove edges of total cost at most B such that an MST in the resulting graph is as heavy as possible. So far, the best approximation algorithm, presented by Frederickson and Solis-Oba (SODA 1996), achieves a factor of O(log(m)). We show that MST interdiction admits an O(1)-approximation. Moreover, this implies an O(1)-approximation for a natural interdiction version of the symmetric traveling salesman problem and the path version thereof.
Automatic MiSe System Software Version 1.4803M | admin login