betaFeedback

WorksComputer Science

Online and Fully-Dynamic Sorting

Abstract

Online sorting asks how to place nn sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: Ω(n)Ω(\sqrt{n}) for online sorting and Ω(n)Ω(n) for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is O(log⁡2n)O(\log^2 n)-competitive and has O(log⁡4n)O(\log^4 n) amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any O(polylog(n))O(\mathrm{polylog}(n)) competitive ratio has amortized recourse at least Ω(log⁡n)Ω(\sqrt{\log n}).(2) For the insertion-only setting, we establish a family of approximation–recourse tradeoffs, including O(log⁡log⁡n)O(\log\log n) competitive ratio with O(log⁡log⁡n)O(\log\log n) amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has (1+ε)n(1+\varepsilon)n space.

Introduction

Maintaining ordered data under online updates is a fundamental algorithmic task. Consider an array of size nn that must store a sequence of elements drawn from a fixed range, say [0,1][0,1]. Elements arrive online, one at a time, and upon arrival must be assigned positions in the array. How should we arrange these elements so as to preserve as much order as possible while performing as little rearrangement as possible?

This question is elegantly captured in the online sorting problem, recently introduced by [2], and further studied by [ABB⁺24, NW26, APV26a, Hu26, KPT26, Her26, PT26, FK26, BBI⁺26, AAB⁺27]. Here, the objective is to insert the elements in the array with the goal of minimizing the sum of absolute differences between consecutive elements in the array. Recent work has developed a rich theory of online sorting, establishing upper and lower bounds on the value of the objective that can be maintained without element rearrangement. The central result is that for element insertions, a competitive ratio of O(n)O(\sqrt{n}) can be achieved [2], and this is tight [2 ABB⁺24]. But, what if we have both element insertions and deletions, i.e., we are in the fully dynamic setting? In this case, it is easy to establish a lower bound of Ω(n)\Omega(n), which matches the trivial upper bound of O(n)O(n) where the elements are re-sorted after each insertion/deletion. So, we ask:

Using limited recourse, can we achieve non-trivial bounds on the competitive ratio of the fully-dynamic sorting problem? Furthermore, using limited recourse, can we also improve on the O(n)O(\sqrt{n}) bound for online (i.e., insertion-only) sorting?

Our Results

Fully-dynamic Sorting. First, we consider the more general problem of fully-dynamic sorting. Our main result is a deterministic algorithm with a O(polylog⁡(n))O(\operatorname{polylog}(n))-competitive ratio, while incurring O(polylog⁡(n))O(\operatorname{polylog}(n)) amortized recourse.

Theorem 1. There is a deterministic algorithm for the fully dynamic sorting problem that maintains an array of size nn under arbitrary insertions and deletions, with competitive ratio O(log⁡2n)O(\log^{2} n) and O(log⁡4n)O(\log^{4} n) amortized recourse per update.

We complement this upper bound with a lower bound showing that any deterministic algorithm with an O(polylog⁡(n))O(\operatorname{polylog}(n)) competitive ratio for this problem must incur Ω(log⁡n)\Omega(\sqrt{\log n}) amortized recourse. So, our upper bound is tight up to the exact exponents in the poly-logs.

Theorem 2. Let 1≤C≤O(n)1 \le C \le O(n). Any deterministic CC-competitive algorithm for fully dynamic sorting with amortized recourse ρ\rho satisfies

ρ=Ω(log⁡nlog⁡C+log⁡n).\rho= \Omega\left(\frac{\log n}{\log C+\sqrt{\log n}}\right).

Insertion-only Sorting. Next, we consider the online (i.e., insertion-only) sorting problem. We show that in this case, we can obtain an exponential improvement over the lower bound in Theorem 2 by giving a deterministic O(log⁡log⁡n)O(\log\log n)-approximation using O(log⁡log⁡n)O(\log\log n) amortized recourse.

Theorem 3. There is a deterministic algorithm for the online sorting problem with competitive ratio O(log⁡log⁡n)O(\log\log n) and O(log⁡log⁡n)O(\log\log n) amortized recourse per insertion.

More generally, we obtain a family of tradeoffs between approximation and amortized recourse in the insertion-only setting, which we present in § 7. In addition to Theorem 3, this tradeoff also yields approximations of O(log⁡n)O(\log n) and O(1)O(1) with O(1)O(1) and O(log⁡n)O(\log n) amortized recourse respectively. These approximation bounds are at least exponentially better than the lower bound of Ω(n)\Omega(\sqrt{n}) that can be obtained without recourse.

Finally, a popular line of work within online sorting explores the problem when the array has extra space. The works of [2 NW26, 4] have shown that with an array of size (1+ε)n(1+\varepsilon)n, one can achieve exponential improvements on the competitive ratio of online sorting. We show that this phenomenon is also true for fully-dynamic sorting. Namely, we give a black-box reduction showing that in an array of size (1+ε)n(1+\varepsilon)n, fully-dynamic sorting reduces to online (i.e., insertion only) sorting with O(1)O(1) overhead in cost and additive O(1/ε)O(1/\varepsilon) overhead in recourse.

Theorem 4. Suppose the array has size (1+ε)n(1+\varepsilon)n for any fixed ε>0\varepsilon> 0. Then every deterministic online sorting algorithm with competitive ratio cc and amortized recourse rr can be transformed into a deterministic fully dynamic sorting algorithm with competitive ratio 2c+12c+1 and amortized recourse r+O(1/ε)r+O(1/\varepsilon) per update.

In particular, Theorems 3 and 4 imply that with (1+ε)n(1+\varepsilon)n space, fully dynamic sorting admits an O(log⁡log⁡n)O(\log\log n) competitive ratio with O(log⁡log⁡n+1/ε)O(\log\log n+1/\varepsilon) amortized recourse.

Our Techniques

Fully-Dynamic Upper Bound (Theorem 1). The high-level idea in fully-dynamic sorting is to move any holes created by element deletions to the end of the array, while keeping the array approximately sorted. Then, insertions can happen only at the end of the array, with local re-sorting and periodic merger of the newly inserted elements into the rest of the array.

To implement the operation of moving a hole efficiently through the array, we recursively organize the array into a data structure that we call a Dynamic Sorting Tree (DST). The challenge is to avoid shifting all intervening elements while ensuring that successive deletions don’t accumulate too much disorder. The DST organizes the array recursively at geometrically decreasing size scales, where a level-ii DST comprises blocks that are themselves composed of sections, each of which is a level-(i−1)(i-1) DST. The sections are labeled either as original or transfer sections, the intuition being the original sections are the ones created when the DST is initialized in sorted order, while the transfer sections allow limited disorder and are created in the process of moving holes through the DST.

Crucially, a transfer section is allowed to contain elements larger than those in the original section that follows it. When a hole reaches the beginning of the original section, we first switch it to the transfer section by changing their shared boundary. No element moves, but the hole is now at the end of the transfer section. We fill this hole with a carefully chosen minimum element from an original section further to the right and in a lower recursive level. The ordering constraints ensure that this element is larger than the receiving transfer section’s existing elements, and so, accepting it requires no shift of its contents. The resulting hole is now in the original section that lost an element, but since we have moved one level down in the recursion, this process can be continued down the recursion tree.

In addition to these moves, we also need to initially move the hole from the position of the deleted element (which can be arbitrary) to the beginning of an original section. This requires further recursive moves within the section containing the deleted element, which are morally similar to moving the hole across the DST albeit at a lower recursive level. Combining these two recursively defined operations, the one that initially moves the hole to the beginning to an original section, and the other that moves it all the way to the end of the array, yields a recourse bound of O(i3)O(i^3) for an ii-level DST. Moving elements and changing section boundaries gradually alters section sizes, which is fixed by periodic calls to a rebuilding operation that reconstitutes a DST that violates its size invariants. Rebuilding is expensive, but it only done occasionally, thereby allowing us to amortize the resulting recourse to a sequence of element deletions preceding it. Finally, the approximation bound is controlled by ordering invariants that we maintain between the different sections in the DST. For a level-ii DST, this yields a cost bound of O(i)O(i) times the overall range of values stored in the DST.

To support insertions as well as deletions, we arrange independent DST components of decreasing depths into an Augmented Dynamic Sorting Tree (A-DST), with no ordering constraints between components. A deletion first routes its hole to the end of its component and then through the subsequent components to the small terminal component, where new elements are inserted. Periodic suffix rebuilding consolidates a suffix into a clean DST and empties its smaller components, maintaining the geometric size bounds. Each such reconstruction is amortized over a number of updates proportional to the suffix’s size bound, contributing only O(d)O(d) amortized recourse for a dd-level structure. The component cost bounds sum to O(d2)O(d^2), while hole routing together with structural rebuilding incurs O(d4)O(d^4) amortized recourse per update. Choosing d=Θ(log⁡n)d = \Theta(\log n) therefore gives an O(log⁡2n)O(\log^2 n) competitive ratio with O(log⁡4n)O(\log^4 n) amortized recourse.

Fully-Dynamic Lower Bound (Theorem 2). Fix a deterministic CC-competitive algorithm. We show that maintaining sorting cost at most C⋅OPTC \cdot\mathrm{OPT} requires large recourse. The adversary works in rounds. Each round starts with the array containing nn equally spaced valued in [0,1][0,1], and has two phases. During the forward phase, the adversary repeatedly deletes an existing element and inserts a copy of 1. At some stage, the adversary switches to the backward phase, where it removes the 1s it had inserted and restores the original elements. This marks the start of the next round. Since all values lie in [0,1][0,1], we always have OPT≤1\mathrm{OPT} \le1, so the algorithm must maintain sorting cost at most CC.

The challenge is to choose the deletions so that the algorithm must either move many elements or incur a large cost. The adversary organizes the original values into a hierarchy of intervals. For each interval IvI_v, some child intervals are labeled targets, that can be further explored for reaching a leaf for deletion, and others buffers, that cannot. The labels are chosen using the algorithm’s current arrangement. The adversary divides the elements of the middle children intervals, in array order, into consecutive groups called windows. It chooses the labels for the children so that a constant fraction of these windows are balanced, meaning that each contains many elements of both types.

If the algorithm moves enough buffer elements, we call the corresponding interval IvI_v paid. These movements contribute to the recourse lower bound, and so the adversary releases its buffer children and allows their elements to be further explored towards a leaf. This lets the adversary continue removing original elements, rather than stopping at buffers for which the algorithm has already incurred the required recourse. The forward phase ends once the adversary cannot remove any additional element using legal search moves.

To bound the cost, we define, for any interval IvI_v, the cost through the interval as the sum of lengths of intersects between IvI_v and the interval spanned by each pair of consecutive array elements. The importance of this parameter is that the total cost of the array is lower bounded by the sum of costs through any set of disjoint intervals. Our main lemma states that for unpaid intervals IvI_v, either many original elements in IvI_v that belonged to target children were not changed to 1, or the cost through IvI_v is large compared to the length of IvI_v. We now use the main lemma recursively to conclude that at most n/4n/4 original elements remain at the end of the forward phase using an appropriate choice of parameters. This implies that there are many paid intervals. An interval that never becomes paid retains at least half of its original elements. Since few original elements remain, the paid intervals at each depth must together have held Ω(n)\Omega(n) elements at the start of the round. Using the definition of a paid interval, this implies that the algorithm must have moved Ω(n)\Omega(n) original buffer elements in total at each depth. We show that these movements can be chosen so that none is counted at two different depths. Summing over the dd depths gives Ω(nd)\Omega(nd) recourse in a round of O(n)O(n) updates, and hence Ω(d)\Omega(d) amortized recourse. Choosing the branching factor and depth appropriately then yields the stated tradeoff with cost CC.

Online (Insertion-Only) Sorting (Theorem 3). Our insertion-only algorithm proceeds in two stages. First, we partition the insertion sequence into geometrically decreasing batches and use the recent online sorting algorithm of [4] to transform each batch into a contiguous sorted block while incurring only O(1)O(1) amortized recourse per element and constant cost. This reduces the problem to maintaining a sequence of sorted blocks in an approximately sorted array. The remaining challenge is to balance two competing objectives: keeping few sorted regions, which leads to a low competitive ratio, and minimizing the number of times each block is re-sorted, which leads to low recourse.

To resolve this tension, we introduce two complementary block gadgets. The Low Recourse Block Gadget organizes the blocks as the leaves of a virtual bb-ary tree and re-sorts the blocks corresponding to completed subtrees. Since every block belongs to only one subtree at each height, it participates in just O(log⁡bk)O(\log_b k) re-sorts, giving O(log⁡bk)O(\log_b k) amortized recourse, at the cost of maintaining up to O(b)O(b) active subtrees per level and hence a competitive ratio of O(blog⁡bk)O(b\log_b k). The High Recourse Block Gadget instead maintains a hierarchy of sorted super-blocks of geometrically increasing capacities, merging a super-block into its parent whenever it becomes full. This ensures that there is only one sorted super-block per level, yielding a competitive ratio of O(log⁡bk)O(\log_b k), but each block may be merged O(b)O(b) times per level, resulting in O(blog⁡bk)O(b\log_b k) amortized recourse. By choosing the branching factor bb, the two gadgets yield complementary approximation–recourse tradeoffs, including O(log⁡n)O(\log n) approximation with O(1)O(1) recourse and O(1)O(1) approximation with O(log⁡n)O(\log n) recourse.

Fully-Dynamic Sorting with (1+ε)(1+\varepsilon)-Space (Theorem 4). For an array with (1+ε)n(1+\varepsilon)n space, we reduce fully dynamic sorting to online sorting, establishing their equivalence in this setting. The reduction periodically rebuilds the array, leaving an empty buffer of size εn\varepsilon n; insertions are handled online, while deletions are deferred until the next rebuild. Rebuilding every εn\varepsilon n updates adds only O(1/ε)O(1/\varepsilon) amortized recourse. We note that, at a high level, our periodic rebuilding strategy is similar in spirit to the reduction from fully-dynamic to online list labeling with extra space in [10], although the technical details of the two reductions are different.

Related Work

Online Sorting. The online sorting problem was introduced by Aamand et al. [2], who established tight deterministic bounds of Θ(n)\Theta(\sqrt{n}) for m=nm=n, later extended to randomized algorithms by Abrahamsen et al. [3]. For m=(1+ε)nm=(1+\varepsilon)n, Aamand et al. [2] established a deterministic lower bound of Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n) and a subpolynomial upper bound. Subsequent works [NW26, APV26a] obtained polylogarithmic upper bounds, with Azar et al. [4] achieving O(log⁡2n/ε)O(\log^2 n/\varepsilon) competitiveness and O(1)O(1) competitiveness with O(nlog⁡2n)O(n\log^2 n) space when the value range is known. Azar et al. [5] extended these results to online metric TSP, which was introduced by [3], obtaining an O(log⁡3n/ε)O(\log^3 n/\varepsilon)-competitive algorithm using m=(1+ε)nm=(1+\varepsilon)n space. They also showed that when opt is unknown, any deterministic algorithm using m=n1+δm = n^{1+\delta} space has competitive ratio Ω(1/δ)\Omega(1/\delta), even for online sorting.

Several variants of online sorting have also been studied. Under stochastic and random-order arrivals, recent works established tight logarithmic bounds [3, 30, 33, 29, 38, 22]. Bercea et al. [6] also studied the problem in the learning-augmented setting, establishing tight consistency robustness tradeoffs. Finally, online sorting techniques have been applied to geometric problems, initially for lower bounds [2]. While recently in [1] several upper bounds for geometric problems are shown, the major one being an O(log⁡2n)O(\log^2 n)-competitive algorithm for online translational packing of convex polygons.

Recourse in Online and Fully-Dynamic Algorithms. Allowing online algorithms to revise earlier decisions while bounding the number of such changes, known as recourse, has proved powerful across a wide range of problems. This includes matching, scheduling, load balancing, and network flows [27 KLS23], Steiner tree and forest [24, 35], and minimum spanning tree and TSP [36]. These works demonstrate that even limited recourse can substantially improve the achievable competitive ratio compared with irrevocable online algorithms.

A closely related line of research studies recourse in the fully-dynamic setting, where elements or requests may both arrive and depart. Bounded-recourse algorithms have been developed for load balancing [21, 17], Steiner tree [25], graph spanners [18], set cover and submodular cover [26, 28, 39, 40, 14], facility location and clustering [19, 34, 23, 13 BCF25a, BCF+25b], and bin packing [20]. More general frameworks for controlling recourse in dynamic settings have also been developed [7].

Online List-Labeling. The online list labeling (also known as file maintenance) problem introduced by [31] asks a complementary question for the same setting of element insertions: what is the minimum recourse of an algorithm that is required to keep the array precisely sorted? For deterministic algorithms, tight bounds of Θ(log⁡2n)\Theta(\log^2 n) and Θ(log⁡n)\Theta(\log n) amortized recourse are known for linear and polynomial space, respectively [16]. Recent randomized algorithms have improved the linear-space upper bound to O(log⁡n⋅polyloglog⁡n)O(\log n \cdot\operatorname{polyloglog} n) [12, 11, 10]. Our work can be interpreted as relaxing the requirement that the array stays perfectly sorted, while allowing bounded recourse.

Organization of the Paper

We begin in Section 3 by giving a simple 2-level data structure that presents some of our ideas in fully-dynamic sorting without the technical complications of the full result. We then introduce the Dynamic Sorting Tree (DST) in Section 4 and build on it to construct the Augmented Dynamic Sorting Tree (A-DST) in Section 5; the A-DST structure realizes Theorem 1. In Section 6, we establish our lower bound for this setting. Section 7 considers the insertion-only setting (online sorting), where we design two new data structures, the Low Recourse Block Gadget and the High Recourse Block Gadget, and use them to yield Theorem 3. Finally, in Section 8, we extend these tradeoffs to the fully dynamic setting with (1+ε)n(1+\varepsilon)n space, establishing Theorem 4. All proofs that are omitted from the main body of the paper appear in the appendix.

Preliminaries

We consider an array of size m≥nm \ge n storing real-valued elements that arrive online, where nn is an upper bound on the number of elements present at any time. Each element occupies a distinct cell, so the array has at least m−nm-n empty cells.

Let S=(x1,…,xk)S=(x_1,\ldots,x_k) denote the elements currently stored in the array, ordered from left to right and ignoring empty cells. The cost of the array is

cost⁡(S)=∑j=1k−1∣xj+1−xj∣.\operatorname{cost}(S)=\sum_{j=1}^{k-1}\lvert x_{j+1}-x_j\rvert.

An optimal offline arrangement sorts the elements and therefore has cost OPT⁡(S)=max⁡S−min⁡S\operatorname{OPT}(S)=\max S-\min S. For sequences containing at most one element, both costs are defined to be zero.

It will be useful to express the cost in terms of threshold crossings. For a threshold z∈Rz\in\mathbb{R}, let cross⁡z(S)\operatorname{cross}_z(S) denote the number of adjacent pairs in SS with one element at most zz and the other greater than zz. Formally,

cross⁡z(S)=∣{j∈[k−1]:(xj>z)≠(xj+1>z)}∣.\operatorname{cross}_z(S)=\left\lvert\left\{j\in[k-1]:(x_j>z)\ne(x_{j+1}>z)\right\}\right\rvert.

For sequences containing at most one element, this number is zero. Since each adjacent pair crosses precisely the thresholds between its two values, summing over all pairs gives

cost⁡(S)=∫Rcross⁡z(S) dz.(1)\operatorname{cost}(S)=\int_{\mathbb{R}}\operatorname{cross}_z(S)\,dz. \tag*{(1)}

The recourse of an update is the number of previously stored elements that change positions during that update. We measure amortized recourse as the total recourse over a sequence of updates divided by the number of updates.

Insertion-Only and Fully Dynamic Updates. We consider two variants of online sorting. In the insertion-only setting, elements arrive one at a time and remain in the array permanently. Upon each arrival, the algorithm must assign the new element to an empty cell, possibly rearranging previously inserted elements.

In the fully dynamic setting, the algorithm must also support deletions of previously inserted elements. A deletion frees the cell occupied by the removed element, and the algorithm may rearrange the remaining elements to maintain a low-cost array. We assume that at most nn elements are present at any time.

Initialization and Reduction to Deletion-Insertion Pairs. We describe our fully dynamic algorithm under the simplifying assumption that updates consist of deletion-insertion pairs. To handle arbitrary update sequences, we initialize an A-DST containing nn virtual elements, all with value 00 and marked as inactive. These elements are initially sorted, and the A-DST is constructed with all transfer sections empty. Since no active elements are present, this initialization incurs no recourse.

When an active element is deleted, we simply mark it as inactive without changing the array. When a new element xx arrives, we choose an arbitrary inactive element yy, delete it from the A-DST, and insert xx using a deletion-insertion pair. Such an inactive element always exists, since immediately before an insertion there are at most n−1n-1 active elements. Thus, the A-DST maintains exactly nn elements throughout the execution, some of which may be inactive. Inactive elements correspond to empty cells in the actual array, but their values are retained internally for comparisons.

The active elements, in their relative order, form a subsequence of the sequence maintained by the A-DST. By the following lemma, a bound on the number of crossings at every threshold for the maintained sequence also holds for the active elements, preserving the competitive guarantee. Moreover, each actual insertion requires only one deletion-insertion pair, while actual deletions incur no recourse. Consequently, the amortized recourse bound for deletion-insertion pairs also applies to arbitrary update sequences.

Lemma 5. Let S′S' be a subsequence of a sequence SS. Then, for every threshold zz, cross⁡z(S′)≤cross⁡z(S)\operatorname{cross}_z(S') \le\operatorname{cross}_z(S). In particular, if cross⁡z(S)≤C\operatorname{cross}_z(S) \le C for every zz, then cost⁡(S′)≤C⋅OPT⁡(S′)\operatorname{cost}(S') \le C \cdot\operatorname{OPT}(S').

Thus, an algorithm that guarantees at most CC crossings at every threshold remains CC-competitive when inactive elements are ignored. For algorithms satisfying this crossing bound, it therefore suffices to analyze deletion–insertion pairs.

Intuition: A 2-Level Data Structure

We first describe a 2-level data structure that captures some of the intuition of our eventual data structures, DST and A-DST, while keeping the technical details much simpler. We then give the actual construction of our data structures in the next two sections, and establish Theorem 1.

By the previous section, we imagine, w.l.o.g., that we start with a sorted array and then handle an alternating sequence of element deletions and insertions. Deleting an element from a sorted array creates a hole. A naïve idea is to move this hole to the end while preserving sorted order, then insert the next element in this hole, and move this element by shifting elements to its position in the sorted order. While this keeps the array precisely sorted, it incurs Θ(n)\Theta(n) recourse in each step. (Throughout this section, nn denotes the size of the array.) Instead, we allow a limited amount of disorder within the array, so that a hole can pass through the array more efficiently.

To illustrate the idea, consider partitioning the array into approximately n\sqrt{n} blocks, each containing approximately n\sqrt{n} elements. We keep the blocks ordered by value, i.e., for two consecutive blocks, all elements in the right block are larger than all elements in the left block. Initially, we also sort the elements within each block.

Now, suppose there is a hole inside a block. With O(n)O(\sqrt{n}) element movements, we can move the hole to the end of the block. Filling the hole with the minimum element of the next block, the hole moves to the beginning of the next block. But, how do we now move the hole to the end of the next block? Doing this naïvely would incur O(n)O(\sqrt{n}) movement in the next block as well, which would create Θ(n)\Theta(n) movement overall across the O(n)O(\sqrt{n}) blocks.

To make this more efficient, we divide each block into a transfer section TT followed by an original section OO. (Initially, TT is empty and the block only has OO.) Each section is individually sorted, but every element of TT is larger than every element of OO. In other words, the two sections are opposite to the sorted order. (For example, see the third block in the final row of Figure 1.) This means that the minimum element of a block is at the beginning of OO, which is adjacent to the maximum element of the block, which is at the end of TT. This adjacency is crucial. Suppose the hole is at the end of TT in a block. We fill this hole with the minimum element of the next block, which is at the beginning of its original section. Since the hole now lies immediately after the transfer section of the next block, we can assign this empty cell to TT by changing the boundary between the two sections. This boundary change moves no elements. This shifts the hole to the end of the transfer section of the next block, thereby recreating our starting configuration in the next block.

References

  1. [1]Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae, Arindam Khan, Linda Kleist, and Csaba D. Tóth. Online geometric packing through online TSP scheduling. In Proceedings of the 2027 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2027. To appear. arXiv:2607.22179.arxiv.org/abs/2607.22179
  2. [2]Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, and Linda Kleist. Online sorting and translational packing of convex polygons. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 1806–1833. SIAM, January 2023. doi:10.1137/1.9781611977554.CH69.DOI
  3. [3]Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, and László Kozma. Online sorting and online TSP: randomized, stochastic, and high-dimensional. In 32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom, volume 308 of LIPIcs, pages 5:1–5:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ESA.2024.5.DOI
  4. [4]Yossi Azar, Debmalya Panigrahi, and Or Vardi. Nearly tight bounds for the online sorting problem. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6642–6658. SIAM, 2026. doi:10.1137/1.9781611978971.237.DOI
  5. [5]Yossi Azar, Debmalya Panigrahi, and Or Vardi. Online metric TSP: Beyond the √n barrier. In 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026, volume 374 of LIPIcs, pages 18:1–18:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.ICALP.2026.18.DOI
  6. [6]Ioana O. Bercea, Gerth Stølting Brodal, John Iacono, László Kozma, and Debmalya Panigrahi. Learning-augmented online sorting and TSP. In 34th Annual European Symposium on Algorithms, ESA 2026, L’Aquila, Italy, August 31 - September 4, 2026, volume 388 of LIPIcs, pages 78:1–78:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.ESA.2026.78.DOI
  7. [7]Sayan Bhattacharya, Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak. Chasing positive bodies. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1694–1714. IEEE, 2023. doi:10.1109/FOCS57990.2023.00103.DOI
  8. [10][BCFC+24a] Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, and Michael Saks. Nearly optimal list labeling. In Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 2253–2274, 2024. doi:10.1109/FOCS61266.2024.00132.DOI
  9. [11][BCFC+24b] Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, and William Kuszmaul. Layered list labeling. Proceedings of the ACM on Management of Data, 2(2):101:1–101:19, 2024. doi:10.1145/3651602.DOI
  10. [12][BCFC+25] Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole Wein. Online list labeling: Breaking the log² n barrier. SIAM Journal on Computing, 54(5), 2025. doi:10.1137/22M1534468.DOI
  11. [13][BCG+24] Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering with fast update time and small resources. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 216–227. IEEE, 2024. doi:10.1109/FOCS61266.2024.00023.DOI
  12. [14][BCP26] Sayan Bhattacharya, Ruoxu Cen, and Debmalya Panigrahi. Fully dynamic set cover: Worst-case recourse and update time. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026, pages 910–921. ACM, 2026. doi:10.1145/3798129.3800805.DOI
  13. [16][BKS12] Jan Bulánek, Michal Koucký, and Michael Saks. Tight lower bounds for the online labeling problem. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 1185–1198, 2012. doi:10.1145/2213977.2214083.DOI
  14. [17][BKSS26] Michael A. Bender, William Kuszmaul, Elaine Shi, and Rose Silver. History-independent load balancing. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1097–1127. SIAM, 2026. doi:10.1137/1.9781611978971.44.
  15. [18][BSS22] Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022, volume 244 of LIPIcs, pages 17:1–17:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ESA.2022.17.DOI
  16. [19][CHP+19] Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3255–3265, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/fface8385abbf94b4593a0ed53a0c70f-Abstract.html.
  17. [20]Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, and David Wajc. Fully-dynamic bin packing with little repacking. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018, volume 107 of LIPIcs, pages 51:1–51:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.51.DOI
  18. [21]Ayoub Foussoul, Vineet Goyal, and Amit Kumar. Fully-dynamic load balancing. Math. Program., 216(1–2):573–603, 2026. doi:10.1007/S10107-025-02310-4.DOI
  19. [22]Chenglin Fan and Mingyu Kang. Optimal high probability bounds for random order online sorting, 2026. arXiv:2610.15438.arxiv.org/abs/2610.15438
  20. [23]Sebastian Forster and Antonis Skarlatos. Dynamic consistent k-center clustering with optimal recourse. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 212–254. SIAM, 2025. doi:10.1137/1.9781611978322.7.
  21. [24]Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: Maintaining a constant-competitive Steiner tree online. SIAM J. Comput., 45(1):1–28, 2016. doi:10.1137/140955276.DOI
  22. [25]Anupam Gupta and Amit Kumar. Online Steiner tree with deletions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 455–467. SIAM, 2014. doi:10.1137/1.9781611973402.34.DOI
  23. [26]Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 537–550. ACM, 2017. doi:10.1145/3055399.3055493.DOI
  24. [27]Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 468–479. SIAM, 2014. doi:10.1137/1.9781611973402.35.DOI
  25. [28]Anupam Gupta and Roie Levin. Fully-dynamic submodular cover with bounded recourse. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1147–1157. IEEE, 2020. doi:10.1109/FOCS46700.2020.00110.DOI
  26. [29]Daniel Anker Hermansen. Optimal stochastic online sorting. In 34th Annual European Symposium on Algorithms, ESA 2026, L’Aquila, Italy, August 31 - September 4, 2026, volume 388 of LIPIcs, pages 142:1–142:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.ESA.2026.142.DOI
  27. [30]Yang Hu. Nearly optimal bounds for stochastic online sorting. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 4969–4995. SIAM, 2026. doi:10.1137/1.9781611978971.180.DOI
  28. [31]Alon Itai, Alan G. Konheim, and Michael Rodeh. A sparse table implementation of priority queues. In Proceedings of the 8th International Colloquium on Automata, Languages and Programming (ICALP), volume 115 of Lecture Notes in Computer Science, pages 417–431. Springer, 1981. doi:10.1007/3-540-10843-2_34.DOI
  29. [33]Andreas Kalavas, Charalampos Platanos, and Thanos Tolias. A polylogarithmic competitive algorithm for stochastic online sorting and tsp. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026), volume 364 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1–58:17, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2026.58.DOI
  30. [34]Jakub Lacki, Bernhard Haeupler, Christoph Grünau, Rajesh Jayaram, and Václav Rozhoň. Fully dynamic consistent k-center clustering. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 3463–3484. SIAM, 2024. doi:10.1137/1.9781611977912.124.DOI
  31. [35]Yaowei Long, Sepideh Mahabadi, Sherry Sarkar, and Jakub Tarnawski. Online Steiner forest with recourse. In 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026, volume 374 of LIPIcs, pages 141:1–141:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPICS.ICALP.2026.141.DOI
  32. [36]Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. SIAM J. Comput., 45(3):859–880, 2016. doi:10.1137/130917703.DOI
  33. [38]Charalampos Platanos and Thanos Tolias. Online sorting with our eyes wide shut. CoRR, abs/2607.17289, 2026. arXiv:2607.17289, doi:10.48550/ARXIV.2607.17289.DOI
  34. [39]Shay Solomon and Amitai Uzrad. Dynamic ((1 + ε) ln n)-approximation algorithms for minimum set cover and dominating set. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1187–1200. ACM, 2023. doi:10.1145/3564246.3585211.DOI
  35. [40]Shay Solomon and Amitai Uzrad. Dynamic set cover with worst-case recourse. In 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026, volume 374 of LIPIcs, pages 153:1–153:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPICS.ICALP.2026.153.DOI

Paper details

vlnc:W_czb9w76x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents