Robustified greedy algorithm improves online resource assignments with lower costs
A Robustified Greedy Algorithm for Online Transportation with Improved Competitive Guarantees
Data Structures and Algorithms
Summary
The paper addresses the challenge of quickly assigning incoming requests to facilities with limited capacity, like delivery trucks or data servers, without knowing future requests. The authors present a new method called Robustified Greedy, which makes smarter decisions by usually assigning requests to the nearest facility but sometimes reassigning to reduce overall cost. This method improves on past algorithms by guaranteeing better performance both generally and specifically in settings like geographic spaces. Experiments show it performs well on real data, keeping assignments close to optimal while relying heavily on nearby matches.
What this means in practice
- •For logistics planners: Assign delivery requests to transportation hubs efficiently in real time, reducing overall routing costs under uncertain demand.
- •For machine learning engineers: Route data or user queries to limited-capacity computational resources or experts online with provably better cost guarantees.
Authors
Ritesh Seth, Syamantak Das, Sharath Raghvendra
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.