BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:11th Colloquium of the Research Area C3 [C3 Kolloquium / Colloquiu
 m of the Research Area C3]
DTSTART:20250718T073000Z
DTEND:20250718T100000Z
DTSTAMP:20260721T132700Z
UID:indico-event-566@math-events.uni-bonn.de
DESCRIPTION:Speakers: Bill Cook (University of Waterloo)\, Luise Puhlmann 
 (Forschungsinstitut für Diskrete Mathematik)\n\nVenue:  Computer Science
  Building (Friedrich-Hirzebruch-Allee 8)\, room 0.016\n09:30    Coffee 
 and Tea (room 2.075)\n10:00    Bill Cook: TSP cut  separation\n10:45 
    Coffee break (room 2.075)\n11:15    Luise Puhlmann: Improved guara
 ntees for the (asymmetric) a priori TSP\n \nBill Cook: TSP cut separation
 \nCutting-plane methods have been used to solve large-scale instances of t
 he traveling salesman problem. The key step requires algorithms for findin
 g linear inequalities valid for all tours\, but violated by the solution t
 o the current linear-programming relaxation. This is known as the cut-sepa
 ration problem. We discuss recent work in TSP cut separation that permitte
 d earlier this year the computation of an optimal 81\,998-stop tour using 
 point-to-point walking distances obtained with the Open Source Routing Mac
 hine (OSRM). The focus of the talk will be on research questions that coul
 d drive further improvements in cutting-plane methods for the TSP and rela
 ted discrete optimization models.\n \nLuise Puhlmann: Improved guarantees
  for the (asymmetric) a priori TSP\nIn the a priori TSP\, we are given a m
 etric space (V\, c) and an activation probability p(v) for each customer v
  \\in V. We ask for a TSP tour T for V that minimizes the expected length 
 after cutting T short by skipping the inactive customers. All known approx
 imation algorithms select a nonempty subset S of the customers and constru
 ct a so called "master route solution"\, consisting of a TSP tour for S an
 d two edges connecting every customer v \\in V \\ S to a nearest customer 
 in S. We analyze how to find the best choice for S when using random sampl
 ing techniques and provide almost matching lower and upper bounds as well 
 as improved approximation guarantees.\nThe asymmetric version (i.e. not re
 quiring c(v\,w) = c(w\,v)) seems to be much harder. We show how to obtain 
 an O(\\sqrt(n))-approximation algorithm\, and also achieve a quasi-polynom
 ial time algorithm with a poly-logarithmic approximation guarantee. Thus\,
  we beat the adaptivity gap (that measures how bad the best a priori tour 
 can be in comparison to the expected length of the a posteriori optimum to
 ur).\nThis is joint work with Jannis Blauth\, Meike Neuwohner\, and Jens V
 ygen (for the symmetric version) and with Manuel Christalla and Vera Traub
  (for the asymmetric version).\n \n\nhttps://math-events.uni-bonn.de/even
 t/566/
LOCATION:Friedrich-Hirzebruch-Allee 8/0-016 - Room 0.016 (Computer Science
  Building)
URL:https://math-events.uni-bonn.de/event/566/
END:VEVENT
END:VCALENDAR