BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:On the Approximability of Train Routing and the MinMax Disjoint Pa
 ths Problem [Oberseminar Discrete Optimization]
DTSTART:20250714T161500Z
DTEND:20250714T171500Z
DTSTAMP:20260615T210000Z
UID:indico-event-328@math-events.uni-bonn.de
DESCRIPTION:Speakers: Britta Peis (RWTH Aachen University)\n\nIn train rou
 ting\, the headway is the minimum distance that must be maintained between
  successive trains for safety and robustness. We introduce a model for tra
 in routing that requires a fixed headway to be maintained between trains\,
  and study the problem of minimizing the makespan\, i.e.\, the arrival tim
 e of the last train\, in a single-source single-sink network. For this pro
 blem\, we first show that there exists an optimal solution where trains mo
 ve in convoys---that is\, the optimal paths for any two trains are either 
 the same or are arc-disjoint.\nVia this insight\, we are able to reduce th
 e approximability of our train routing problem to that of the min-max disj
 oint paths problem\, which asks for a collection of disjoint paths where t
 he maximum length of any path in the collection is as small as possible.\n
 While min-max disjoint paths inherits a strong inapproximability result on
  directed acyclic graphs from the multi-level bottleneck assignment proble
 m\, we show that a natural greedy composition approach yields a logarithmi
 c approximation in the number of disjoint paths for series-parallel graphs
 .\nWe also present an alternative analysis of this approach that yields a 
 guarantee depending on how often the decomposition tree of the series-para
 llel graph alternates between series and parallel compositions on any root
 -leaf path.\nJoint work with Umang Bhaskar\, Katharina Eickhoff\, Lennart 
 Kauther\, Jannik Matuschke and Laura Vargas Koch\n \nThe Oberseminar take
 s place in the Seminarraum\, 1st floor. Participants are invited to have c
 offee or tea in the lounge before.\n \n\nhttps://math-events.uni-bonn.de/
 event/328/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/328/
END:VEVENT
END:VCALENDAR