BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquim - Improving Christofides' Algorithm with Randomizatio
 n and LP
DTSTART:20131122T151500
DTEND:20131122T163000
DTSTAMP:20260407T025847Z
UID:b16321e73c8235e04b766bd6e12d79363876faf83b0be3b64774455f
CATEGORIES:Conferences - Seminars
DESCRIPTION:David Shmoys - Cornell University\nAbstract:\nIn 1976\, Christ
 ofides gave an approximation algorithm for the traveling salesman problem 
 (TSP) with metric costs that was guaranteed to find a tour that was no mor
 e than 3/2 times the length of the shortest tour visiting a given set of n
  cities\; it remains an open problem to give a polynomial-time algorithm w
 ith a better performance guarantee.\nWe shall survey a number of recent re
 sults that have yielded improvements for significant special cases\, and f
 or related problems. Most importantly\, there is now an algorithm conjectu
 red to have a stronger guarantee. This algorithm emerged from a stream of 
 work starting with a paper of Asadpour\, Goemans\, Madry\, Oveis Gharan\, 
 and Saberi\, and was proposed by Oveis Gharan\, Saberi\, and Singh. An\, K
 leinberg\, and Shmoys show that a simpler variant\, in the case of the s-t
  path TSP\, improves upon Christofides¹ algorithm for general metric cost
 s. Furthermore\, Gao showed how to obtain a tight LP-based analysis for th
 e s-t path TSP with costs derived as shortest paths in an underlying unwei
 ghted undirected graph.\nShort bio:\nDavid Shmoys obtained his Ph.D. in Co
 mputer Science from the University of California at Berkeley in 1984\, and
  held a faculty position at MIT before joining the Cornell faculty. He is 
 the the director of the School of Operations Research and Information Engi
 neering at Cornell\, Co-Chair of the Academic Planning Committee for Corne
 ll NYC Tech\, and Associate Director of the Institute of Computational Sus
 tainability at Cornell University. In addition\, he is a Fellow of the ACM
 \, INFORMS\, and of SIAM\, was an NSF Presidential Young Investigator.\nSh
 moys' research has focused on the design and analysis of efficient algorit
 hms for discrete optimization problems\, with applications including sched
 uling\, inventory theory\, computational biology\, and most recently\, com
 putational sustainability. His work has highlighted the central role that 
 linear programming plays in the design of approximation algorithms for NP-
 hard problems\; his recent book\, co-authored with David Williamson)\, The
  Design of Approximation Algorithms\, was awarded the 2013 Lanchester Priz
 e by INFORMS.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR