CS Paper Radar

A Robustified Greedy Algorithm for Online Transportation with Improved Competitive Guarantees

Ritesh Seth, Syamantak Das, Sharath Raghvendra

cs.DS ·submitted 2026-09-30 05:59 UTC · v1

Abstract

We study the \emph{online transportation problem}, in which $n$ requests arriving sequentially in a metric space must be irrevocably assigned to $k$ capacitated facilities. Beyond classical logistics applications, this problem models resource-allocation tasks arising in machine learning, including online facility assignments, recommender systems, and mixture-of-experts routing. We introduce \emph{Robustified Greedy} (RG), a deterministic generalization of the Robust Matching algorithm that achieves a competitive ratio of $6.6604k-2.89$, improving upon the state-of-the-art bounds of $8k-7$ (Arndt et al., SOSA 2026) and $8k-5$ (Harada and Itoh, ICALP 2025). RG also retains the metric-sensitive guarantee established for Robust Matching (RM) (Nayyar and Raghvendra, FOCS 2017), achieving a competitive ratio of $O(k^{1-1/d}\log^2 n)$ in $d$-dimensional Euclidean spaces for fixed $d>1$. No comparable metric-sensitive guarantee is known for the transportation algorithms of Arndt et al.\ or Harada and Itoh. Beyond these competitive guarantees, RG provides a simple explanation for its decisions. It favors the natural nearest-neighbor assignment and, for suitable parameters, departs from this choice only when it identifies a reassignment that reduces the cost of its maintained auxiliary matching, thereby correcting accumulated assignment costs. We also prove that nearest-neighbor assignments account for a guaranteed fraction of RG's total cost, approaching one-half for appropriate parameters, even under adversarial arrivals. Experiments on real-world datasets corroborate the theory: RG achieves lower cost-to-\textsc{Opt} ratios than the competing algorithms while retaining a substantial nearest-neighbor component in its cost.

Closest papers

Nearest neighbours by meaning across the whole index.

Online Transportation via Shifted Geometric Scales

cs.DS ·2026-11-12 ·John Jeang
theory similarity 0.78
Abstract · The majority of this work was generated and edited by iteratively prompting ChatGPT-6 Astra. After review, we believe the results to be corr…

In the Online Transportation problem, introduced by Kalyanasundaram and Pruhs (1995), requests arrive sequentially in a metric space and must be assigned immediately and irrevocably to one of $m$ facilities with available capacity. The objective is to minimize the total distance between requests and their assigned facilities. The problem generalizes the Online Metric Matching problem, in which each facility has unit capacity, and inherits a $2m-1$ lower bound on the competitive ratio for all deterministic algorithms. For Online Metric Matching, Kalyanasundaram and Pruhs (1993) and Khuller, Mitchell, and Vazirani (1994) established an optimal deterministic competitive ratio of $2m-1$, attained by the Retrospective (Permutation) algorithm. Kalyanasundaram and Pruhs (1998) conjectured that the same ratio is achievable for online transportation. Recently, Seth, Das, and Raghvendra (2026) obtained a competitive ratio of approximately $6.66m-2.89$ using their Robustified Greedy algorithm. We give an algorithm with competitive ratio $ρ(m-1)+1$, where $ρ\approx5.64$. Our algorithm builds on minimum-spanning-tree search techniques developed by Harada and Itoh (2025) and Arndt, Moseley, Pruhs, and Uetz (2026), using priority-based virtual depth-first searches over the known facilities. However our algorithm uses a phase to shift the geometric search scales, to decide when to skip certain searches and optimize the thresholds that define what edges to include in a given search.

0.14

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

cs.DS ·2026-09-18 ·Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor +1 more
similarity 0.67
Abstract

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

0.19

Optimal analysis of Greedy for stochastic online Euclidean matching: flat torus to the rescue

cs.DS ·2026-09-20 ·Mingwei Yang, Sophie H. Yu
theory similarity 0.65
Abstract

We study online metric matching with $n$ servers and $n$ requests, all sampled independently and uniformly from $[0,1]^d$. We analyze the Greedy algorithm, which matches each arriving request to its closest available server. Despite its strong empirical performance, non-trivial bounds on Greedy's competitive ratio were previously known only for $d = 1$, where it is $O(1)$-competitive [BFP23]. We prove that Greedy is $O(1)$-competitive for every fixed $d\geq3$ and has competitive ratio $Θ(\sqrt{\log n})$ for $d=2$. Our proof first analyzes Greedy on the flat torus and then transfers the resulting estimates to the cube.

0.40

The Online $k$-Taxi Problem Is Competitive on All Metrics

cs.DS ·2026-11-04 ·Christian Coester, Yichen Huang, Tze-Yang Poon
similarity 0.65
Abstract

The online $k$-taxi problem is a natural generalization of the $k$-server problem: $k$ taxis must serve a sequence of requests in a metric space. Each request is a pair of points $(r,s)$, and the algorithm serves the request by first moving a taxi to $r$ (to pick up a passenger) and then to $s$ (to drop off the passenger). The cost is the total distance traveled by the taxis without a passenger. Previous bounds for general $k$ all depended on the number of points $n$ or the aspect ratio $Δ$ of the metric space, both of which can be infinite on general metrics, and competitive algorithms were previously known on general metrics only for $k \le 3$. In this work, we give a $9^{k-1}$-competitive randomized algorithm against adaptive online adversaries and, as a corollary, an $81^{k-1}$-competitive deterministic algorithm for the online $k$-taxi problem.

0.10

Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies

cs.DS cs.CCcs.GTecon.TH+1 ·2026-10-09 ·Nick Arnosti, Rad Niazadeh, Pranav Nuti, Felipe Simon
benchmarktheory similarity 0.65
Abstract

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

0.39

Building On Learning-Augmented Online Sorting

cs.DS ·2026-10-29 ·Wyatt Olson
similarity 0.63
Abstract · 5 pages, 0 figures

Online sorting is a problem that has gained attention recently, and is a natural translation of sorting into an online setting. The problem at hand is to place elements of an online sequence immediately and irrevocably with the goal of producing an array that is as close to sorted as possible upon inserting all elements. Recent work by Bercea et al. [ESA 2026] introduced the incorporation of learned predictions into the online sorting domain. They show lower bounds for the consistency and robustness of any algorithm, including randomization, then provide a deterministic algorithm that is $O(n/r)$-consistent and $O(r)$-robust, which are tight bounds. However, this algorithm requires prior knowledge of the optimal offline cost of the full input sequence before all elements have been revealed. We resolve this by providing an algorithm with matching bounds that does not require knowledge of the optimal cost, then extend these results to the more general problem of online metric TSP, in line with the prior work.

0.14

A Deterministic O(log m)-Competitive Algorithm for Online Minimum Cost Bipartite Matching with Delays

cs.DS ·2026-11-01 ·Tung-Wei Kuo
theory similarity 0.63
Abstract

In the online Minimum cost Bipartite Perfect Matching with Delays (MBPMD) problem, $m$ requests and $m$ servers arrive over time in a metric space. An online algorithm has to match each request to a server and can postpone a matching decision by paying the delay cost. The objective is to minimize the total distance and delay cost. Azar, Chiplunkar, and Kaplan gave a randomized $O(\log n)$-competitive algorithm for metric spaces with $n$ points that are known in advance. For deterministic algorithms, however, the best known competitive ratio in general metric spaces was $O(m^{0.59})$, due to Azar and Jacob-Fanani. On the line, Kuo proposed the Virtual Robust Matching (VRM) algorithm and showed that it is $O(\sqrt{m}\log^2 m)$-competitive. We prove that VRM is $O(\log m)$-competitive for the MBPMD problem in any metric space. VRM is deterministic and does not need to know the metric space or $m$ in advance. It is the first deterministic polylogarithmic-competitive algorithm for the MBPMD problem in general metric spaces. Unlike the previous analysis of VRM, our analysis does not rely on a geometric decomposition of the metric space. Instead, it charges the waiting time of requests over time to the edges of a fixed optimal matching. We also extend VRM to the non-bipartite version and prove that the resulting deterministic algorithm is $O(\log m)$-competitive. This improves the $O(\log^5 m)$ bound of Dufay and Wattenhofer and matches a concurrent result of Ahmadian, Chawla, Kumar, Purohit, and Zhang. The proof that VRM is $O(\log m)$-competitive and its non-bipartite extension were found by GPT-6 Astra (OpenAI) with almost no human input. We used Claude Opus 5.5 (Anthropic) to simplify and present the results. See the AI Usage and Methodology section for details. We take full responsibility for this paper.

0.20

Near-Optimal Online Metric Matching on $Δ$-ary HST

cs.DS cs.CCcs.DM ·2026-09-21 ·Parth Gor, Sourya Roy, Kasturi Varadarajan
similarity 0.62
Abstract

In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request must be matched to a server that was not matched to a previous request. The goal is to minimize the matching cost. For randomized algorithms with an oblivious adversary, the best known competitive ratio is obtained by embedding the metric space into an HST, and then solving the problem in the setting where the metric space is defined by the HST. Bansal et al. (Algorithmica, 2014) introduced a framework for online metric matching where one develops an algorithm in a restricted reassignment model, and then transforms this into a true online algorithm. Using this framework, they obtained an expected competitive ratio of $O(\log n)$ for HSTs; this also gives the best known competitive ratio of $O(\log^2 n)$ for general metrics. In this paper, we revisit this framework with the aim of developing new algorithms. For HSTs where each node has at most $Δ$ children, we develop an algorithm via this framework with an expected competitive ratio of $O((\log\log Δ) \cdot \log Δ)$. In particular, this ratio is independent of $n$, the number of servers/requests. It is near-optimal, as the expected competitive ratio of any algorithm is $Ω(\log Δ)$.

0.16