2026-10-01T07:51:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25547 2026-09-23T23:43:33Z ddc:004 open_access

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP Kalavas, Andreas Platanos, Charalampos Tolias, Thanos sorting online algorithm balls-into-bins TSP In Online Sorting, an array of n initially empty cells is given. At each time step t, an element x_t ∈ [0,1] arrives and must be irrevocably placed in an empty cell without knowledge of future arrivals. We aim to minimize the sum of absolute differences between pairs of elements placed in consecutive array cells, seeking an online placement strategy that results in a final array close to a sorted one. An interesting multidimensional generalization, referred to as the Online Traveling Salesperson Problem, arises when the request sequence consists of points in the d-dimensional unit cube and the objective is to minimize the sum of Euclidean distances between points in consecutive cells. Motivated by the recent work of (Abrahamsen, Bercea, Beretta, Klausen and Kozma; ESA 2024), we consider the stochastic version of Online Sorting (resp. Online TSP), where each element (resp. point) x_t is an i.i.d. sample from the uniform distribution on [0, 1] (resp. [0,1]^d). By carefully decomposing the request sequence into a hierarchy of balls-into-bins instances, where the balls to bins ratio is large enough so that bin occupancy is sharply concentrated around its mean and small enough so that we can efficiently deal with the elements placed in the same bin, we obtain an online algorithm that approximates the optimal cost within a factor of O(log² n) with high probability. Our result comprises an exponential improvement over the previously best known competitive ratio of Õ(n^{1/4}) for Stochastic Online Sorting due to (Abrahamsen et al.; ESA 2024) and O(√n) for (adversarial) Online TSP due to (Bertram, ESA 2025). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Kalavas and Charalampos Platanos and Thanos Tolias 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.58 urn:nbn:de:0030-drops-255473 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.58 eng https://creativecommons.org/licenses/by/4.0/legalcode