Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Monday, August 22, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Naveen Garg (IIT New Delhi)
The Held-Karp bound is one of the better known lower bounds on the cost of a traveling salesman tour. In this talk I will present an algorithm for computing a 1+ε approximation to the Held-karp bound in time O((m/ε)2). Our algorithm is a Lagrangean relaxation algorithm and uses minimum weight branching computations as a subroutine.
Automatic MiSe System Software Version 1.4803M | admin login