Campus Event Calendar
Event Entry
What and Who
Online Sorting and Online TSP
Jonas Klausen
Ph.D. student at the University of Copenhagen
AG1 Advanced Mini-Course
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 3 December 2024
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In the online sorting problem, n items are revealed one by one and have to be placed (immediately and irrevocably) into empty cells of a size-n array. The goal is to minimize the sum of absolute differences between items in consecutive cells. This natural problem was recently introduced by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) as a tool in their study of online geometric packing problems. They showed that when the items are reals from the interval [0,1] a competitive ratio of O(√n) is achievable, and no deterministic algorithm can improve this ratio
asymptotically.
In this paper, we extend and generalize the study of online sorting in three directions:
- randomized: we settle the open question of Aamand et al. by showing that the O(√n) competitive ratio for the online sorting of reals cannot be improved even with the use of randomness;
- stochastic: we consider inputs consisting of n samples drawn uniformly at random from an interval, and give an algorithm with an improved competitive ratio of Õ(n^{1/4}). The result reveals connections between online sorting and the design of efficient hash tables;
- high-dimensional: we show that Õ(√n)-competitive online sorting is possible even for items from ℝ^d, for arbitrary fixed d, in an adversarial model. This can be viewed as an online variant of the classical TSP problem where tasks (cities to visit) are revealed one by one and the salesperson assigns each task (immediately and irrevocably) to its timeslot. Along the way, we also show a tight O(log n)-competitiveness result for uniform metrics, i.e., where items are of different types and the goal is to order them so as to minimize the number of switches between consecutive items of different types.
This talk will introduce the problem of online sorting, give intuition for the lower bound, and sketch out possible future directions of study. This talk is based on joint work with Mikkel Abrahamsen, Ioana Bercea, Lorenzo Beretta, and László Kozma, available at https://doi.org/10.4230/LIPIcs.ESA.2024.5
asymptotically.
In this paper, we extend and generalize the study of online sorting in three directions:
- randomized: we settle the open question of Aamand et al. by showing that the O(√n) competitive ratio for the online sorting of reals cannot be improved even with the use of randomness;
- stochastic: we consider inputs consisting of n samples drawn uniformly at random from an interval, and give an algorithm with an improved competitive ratio of Õ(n^{1/4}). The result reveals connections between online sorting and the design of efficient hash tables;
- high-dimensional: we show that Õ(√n)-competitive online sorting is possible even for items from ℝ^d, for arbitrary fixed d, in an adversarial model. This can be viewed as an online variant of the classical TSP problem where tasks (cities to visit) are revealed one by one and the salesperson assigns each task (immediately and irrevocably) to its timeslot. Along the way, we also show a tight O(log n)-competitiveness result for uniform metrics, i.e., where items are of different types and the goal is to order them so as to minimize the number of switches between consecutive items of different types.
This talk will introduce the problem of online sorting, give intuition for the lower bound, and sketch out possible future directions of study. This talk is based on joint work with Mikkel Abrahamsen, Ioana Bercea, Lorenzo Beretta, and László Kozma, available at https://doi.org/10.4230/LIPIcs.ESA.2024.5
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
897 027 2575
passcode not visible
logged in users only
Nidhi Rathi, 12/02/2024 11:17
Nidhi Rathi, 11/29/2024 14:55 -- Created document.
Nidhi Rathi, 11/29/2024 14:55 -- Created document.