Campus Event Calendar
Event Entry
What and Who
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Lazar Milenkovic
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 22 October 2019
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We study the bottleneck asymmetric traveling salesman problem, a variant of the traveling salesman problem where the objective is to minimize the maximum edge cost in a tour, rather than the sum of the edge costs. While the edge costs satisfy the triangle inequality, they are not necessarily symmetric, meaning that the distance from node a to node b might not be the same as the distance from node b to node a.
Our main contribution is a simple 4 log_2 n-approximation algorithm for the bottleneck asymmetric traveling salesman problem. In addition, we give a constant factor approximation for the restricted version of a problem where every edge lies on a cycle of a bounded length. Finally, we give a new linear programming-based algorithm that achieves a constant factor approximation for the undirected version of the problem. Although the latter is not optimal in terms of the approximation factor, we study it in the hope to gain some insights for the directed graphs.
Contact
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 10/16/2019 08:50
Karl Bringmann, 10/11/2019 17:41
Karl Bringmann, 10/11/2019 17:41 -- Created document.
Karl Bringmann, 10/11/2019 17:41
Karl Bringmann, 10/11/2019 17:41 -- Created document.