Tag - Travelling salesman problem

Ola Svensson: Polyhedral Techniques in Combinatorial Optimization: Matchings and Tours

5th October, 2023

We overview recent progress on two of the most classic problems in combinatorial optimization: the matching problem and the travelling salesman problem. We focus on deterministic parallel algorithms for the perfect matching problem and the first constant-factor approximation algorithm for the asymmetric travelling salesman problem. While these questions pose seemingly different challenges, recent progress has been achieved using similar polyhedral techniques. In particular, for both problems, we will explain the use linear programming formulations, even exponential-sized ones, to extract structure from problem instances to guide the design of better algorithms.

Anna Erschler: Ordering Ratio Function and Travelling Salesman Breakpoint for Groups and Metric Spaces

4th December, 2020

(Abstract taken from arXiv paper.) We study asymptotic invariants of metric spaces and infinite groups related to the universal Travelling Salesman Problem (TSP). We prove that spaces with doubling property (in particular virtually nilpotent groups) admit Gap for Ordering Ratio functions which holds for all orders on these spaces. We describe Travelling Salesman Breakpoint for finite graphs. We characterize groups with Travelling Salesman Breakpoint ≤ 3 as virtually free ones. We show that Ordering Ratio function is bounded (which is the best possible situation) for all uniformly discrete δ-hyperbolic spaces of bounded geometry, in particular for all hyperbolic groups. We prove that any metric space, containing weakly a sequence of arbitrarily large cubes, has infinite Travelling Salesman Breakpoint; this means that any order on such spaces satisfies OR(s)=s for all s. This is the worst possible case for Ordering Ratio functions. For a sequence of finite graphs, we provide a sufficient spectral condition for OR(s)=s. This condition is in particular satisfied for any sequence of expander graphs. Under this stronger assumption of being a family of expander graphs, we prove a stronger claim about snakes of bounded width. We show that any metric space of finite Assouad-Nagata dimension admits an order satisfying OR(s) ≤ Const ln s, and discuss general Gap Problems for Ordering Ratio functions.