Online Metric TSP: Beyond the √n Barrier

We study an online variant of the Traveling Salesperson Problem (TSP) in which n points arrive sequentially and must be inserted into an evolving tour. In the classical setting where arbitrary insertions are allowed, an O(log n)-competitive algorithm has been known since the 1970s (Rosenkrantz, Stearns and Lewis 1977, Imase and Waxman 1991). Recently, Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA 2024] introduced online metric TSP, a stricter model in which each arriving point must be assigned to a distinct cell of an array of size m ≥ n, with the final tour order induced by the non-empty cells; the parameter m captures the space usage of the algorithm. When m = 2ⁿ, this model recovers arbitrary insertions and therefore admits an O(log n)competitive algorithm. In contrast, when m = n, i.e., when each point's position is fixed on arrival, Bertram [7] recently showed that the competitive ratio is Θ(√n). We investigate the tradeoff between space usage and competitiveness between these extremes. We note that this tradeoff was previously explored by the authors in [6] for the online sorting problem, which is the special case of online metric TSP on a line metric. Our main result is a deterministic online metric TSP algorithm using m = (1 + ε)n space that achieves a competitive ratio of O(log³ n/ε), for any ε ≤ 1. In particular, increasing the space from n to 2n improves the competitive ratio from Θ(√n) to O(log³ n). We complement this with a lower bound showing that for m = n^1+ε, any deterministic algorithm has a competitive ratio Ω(1/ε), for all ε ≥ Ω(log log n/log n). Consequently, even with m = O(n · polylog(n)), deterministic algorithms cannot achieve a constant competitive ratio.

Duke Scholars

Author Debmalya Panigrahi Computer Science