Competitive Online Transportation Simplified

Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Marc Uetz · 2025

Read Competitive Online Transportation Simplified by Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Marc Uetz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08381.txt.

Introduction

Stephen Arndt, Benjamin Moseley, Kirk Pruhs, and Marc Uetz present a 2025 paper on the online transportation problem. Cars arrive over time in a space with garages of varied size. Each car must be sent to a garage at once, with no later changes, and the aim is to cut the total distance driven.

In 1998, a strong bound for fast algorithms was proposed as a conjecture, matching the best bound for a simpler matching problem. A recent paper gave the first proof with a cost within a simple factor of that bound. Arndt and co-authors offer a new algorithm and proof that they believe is simpler. A cleaner proof can help others extend the result to new settings.

Catalog record

CREATORStephen Arndt, Benjamin Moseley, Kirk Pruhs, Marc Uetz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08381

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Competitive Online Transportation Simplified Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Marc Uetz Abstract The setting for the online transportation problem is a metric space M M , populated by m m parking garages of varying capacities. Over time cars arrive in M M , and must be irrevocably assigned to a parking garage upon arrival in a way that respects the garage capacities. The objective is to minimize the aggregate distance traveled by the cars. In 1998, Kalyanasundaram and Pruhs conjectured that there is a ( 2 ​ m − 1 ) (2m-1) -competitive deterministic algorithm for the online transportation problem, matching the optimal competitive ratio for the simpler online metric matching problem. Recently, Harada and Itoh presented the first O ⁡ ( m ) O(m) -competitive deterministic algorithm for the online transportation problem. Our contribution is an alternative algorithm design and analysis that we believe is simpler. 1 Introduction Let us start by defining the problem: Online Transportation Problem Definition: The setting for the online transportation problem is a metric space M=(X,d) , consisting of a collection X of points/locations, and a distance function d:X^{2}\rightarrow\mathbb{R}^{+} that specifies the distance between pairs of points in X . The metric space M is populated by m parking garages 1,2,\dots,m at the collection of locations G=\{g_{1},g_{2},\ldots,g_{m}\} , where each g_{i}\in X . Further each garage i has a positive integer capacity c_{i} , which is conceptually the number of parking spaces in garage i . At each integer unit of time t , 1\leq t\leq k , a car t arrives at some location x_{t}\in X , where k=\sum_{i=1}^{m}c_{i} . After the online algorithm sees the location x_{t} it must irrevocably assign car t to a garage i of its choice, subject to the constraint that strictly less than c_{i} cars have been previously assigned to garage i , incurring a movement cost of d(x_{t},g_{i}) . The objective is to minimize the total movement (cost) of the cars. 1.1 The Story to Date A widely-studied special case of the online transportation problem is the online metric matching problem. In the online metric matching problem, all of the garages have unit capacity. At the dawn of the halcyon era of competitive analysis of online algorithms, circa 1990, it was shown that: • The natural greedy algorithm, which parks each car in the nearest available garage, is \left(2^{m}-1\right) -competitive [ 10 ] . • The Retrospective/Permutation algorithm is (2m-1) -competitive [ 10 , 14 ] . The Retrospective algorithm maintains the invariant that residual capacity of each garage is the same as residual capacity for that garage in the optimal matching of the cars that have arrived to date. • The competitive ratio of every deterministic algorithm on a star metric space is at least 2m-1 [ 10 , 14 ] . So for a general metric space, the Retrospective algorithm is optimally competitive among deterministic algorithms. In the mid 1990’s, one of the three natural followup research directions/questions, proposed in [ 11 ] , was to determine the the optimal deterministic competitive ratio for the online transportation problem. In fact it was conjectured that: Conjecture 1 . [ 11 ] There is a (2m-1) -competitive deterministic algorithm for the online transportation problem. So essentially this conjecture hypothesizes that arbitrary-capacity garages are no harder for an online algorithm than unit-capacity garages. It was observed early on that the analysis of the natural greedy algorithm for the online metric matching algorithm is also valid in the online transportation problem, so the natural greedy algorithm is \left(2^{m}-1\right) -competitive for online transportation [ 11 ] . In contrast, the competitive ratio of the Retrospective algorithm for online transportation is not bounded by any function of m [ 11 ] . There are two hurdles that researchers faced when trying to find a (nearly) optimally-competitive algorithm for online transportation. The first hurdle is an algorithm design issue. In particular, it is not clear how the garage capacities should affect the design of the algorithm. One natural hypothesis is that the “right” algorithm should try to load balance between garages, favoring sparsely-filled garages over nearly-full garages. In 1995, this intuition led to a result showing that a modification of the natural greedy algorithm, where the distance to garages that are more than half full is artificially doubled, is O(1) -competitive for online transportation with resource augmentation, that is when comparing to the optimal objective value with garages of half the capacity [ 13 ] . But this approach essentially hit a dead end, as such algorithms are not readily adaptable to be close to O(m) -competitive for online transportation without resource augmentation. The second, seemingly higher, hurdle is an algorithmic analysis issue. In the (2m-1) -competitiveness analysis of the Retrospective algorithm, the distance that the Retrospective algorithm moves each car is upper-bounded by twice the cost of the (entire) optimal matching. In the online transportation problem, due to there being potentially significantly many more cars than garages, the distance that the online algorithm moves a car has to be upper-bounded by only a portion, say the cost of an edge for example, of the optimal matching. Identifying that portion/edge to charge is challenging for the known algorithms that are candidates for being O(m) -competitive for online transportation. As an illustrative example of this analysis difficulty, consider the Robust Matching (RM) algorithm [ 19 ] . Roughly speaking the RM algorithm tries to simultaneously approximate both the natural greedy algorithm and the Retrospective algorithm, by both always parking each car in a garage that is within a constant factor of being the closest, and by maintaining the invariant that the residual capacity of each garage is the same as the residual capacity for that garage in some constant-approximate optimal matching of the cars that have arrived to date [ 19 ] . In particular, the RM algorithm does not, in any overt way, take the fullness of the various garages into account. The name Robust Matching was given to this algorithm when it was introduced into the literature in 2016 [ 19 ] , although the algorithm, and the closely-related generalized work function algorithm, were known as reasonable candidate algorithms in the mid 1990’s. While it seems likely (at least to us) that the RM algorithm is O(m) -competitive for the online transportation problem, the best competitiveness anyone can show is O(m\log^{2}k) [ 8 , 17 ] . The challenge of establishing O(m) -competitiveness for RM is determining how to charge RM’s movement of individual cars to portions/edges in the optimal matching. Finally, after 30 years, in 2025, a deterministic O(m) -competitiveness result for online transportation was obtained [ 8 ] . At a high level this result surmounted the analysis issue by designing an algorithm, which we will call the Star Decomposition algorithm, with the Most Preferred Free Servers (MPFS) property, which means that the garage that the algorithm picks to park a car only depends on the location of the garages and the car’s arrival location (not on how full the garages are, not on where previous cars were parked, etc.). It was observed in [ 9 ] that, like the natural greedy algorithm, upper bounds on the

Read the complete text