BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Effective-Resistance-Reducing Flows\, Spectrally Thin Trees and As
 ymmetric TSP
DTSTART:20150210T160000
DTEND:20150210T170000
DTSTAMP:20260407T100406Z
UID:06bfdb4f0a8147b7ac7f3e8355bc1d3c759b5f2f85cbd30a62e92999
CATEGORIES:Conferences - Seminars
DESCRIPTION:Shayan Oveis Gharan  (University of Washington)\nWe show that
  the integrality gap of the natural LP relaxation\nof the Asymmetric Trave
 ling Salesman Problem (ATSP) is at most polyloglog(n). In other words\, th
 ere is a polynomial time algorithm that approximates the value of the opti
 mum tour within a factor of polyloglog(n).\nThis is the first significant 
 improvement over the classical O~(log n) approximation factor for ATSP. Ou
 r proof builds on recent developments in operator theory\, in particular r
 ecent resolution of the Kadison Singer conjecture by Marcus\, Spielman and
  Srivastava.\nIn this talk\, I will highlight the main ideas of our proof.
 \nThis is a joint work with Nima Anari.\nShort bio:\nShayan Oveis Gharan 
  is an assistant professor at CSE department at UW. He received his PhD fr
 om the MS&E department at Stanford University. Before joining UW he spent 
 one and a half years as a postdoctoral Miller fellow at UC Berkeley where 
 his host was Umesh Vazirani. He has done his undergraduate studies at the 
 Computer Engineering department at Sharif University.\nHis main research i
 ncludes Algorithm design\, Graph Theory and Applied Probability. He has re
 ceived several awards for his works on Traveling Salesman Problem.
LOCATION:INF 211
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR