Source-linked AI summary
A Robustified Greedy Algorithm for Online Transportation with Improved Competitive Guarantees
Ritesh Seth, Syamantak Das, Sharath Raghvendra
TL;DR
Online transportation asks how to assign arriving requests irrevocably to capacitated servers when future requests are unknown. This paper introduces Robustified Greedy, which combines nearest-server choices with an auxiliary matching, and proves improved competitive guarantees. Its bound is 6.6604k−2.89, and its decisions retain a substantial nearest-neighbor component.
Problem
Online transportation requires irrevocable assignments to capacitated servers, and matching-based guarantees do not directly yield guarantees depending on k rather than total capacity n.
Source: §1 · pp. 1–2Method
Robustified Greedy generalizes Robust Matching with a parameter α that favors nearest-server assignments when α<t while maintaining an auxiliary offline matching.
Source: §1 · p. 3Results
RG’s competitive ratio is at most 6.6604k−2.89, independent of total capacity n, and it retains the metric-sensitive O(k^(1−1/d)log^2 n) guarantee in fixed-dimensional Euclidean spaces.
Source: §1 · p. 3, §8 · p. 24Takeaways & Limitations
RG’s structure makes non-greedy choices interpretable as responses to accumulated auxiliary-matching cost, while a substantial fraction of its total cost comes from nearest-neighbor assignments.
Source: §8 · p. 24The stated path classification fixes t>1 and 1≤α≤t; the input-sensitive convention sets μ_X(S)=1 when DIAM(S)=0.
Source: §1 · p. 4, §6 · p. 14
Abstract
from arXiv · showhide
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.
1 Introduction
Online transportation requires irrevocable assignments to capacity-limited servers, with performance judged against an optimum that knows the full sequence. Robustified Greedy favors nearest-server assignments while improving the known competitive guarantee for transportation.
Motivation
- Obtaining a deterministic guarantee linear in k and independent of total capacity remained open for more than two decades before recent 8k−5 and 8k−7 bounds.The 2k−1 conjecture matches the known lower bound.Source: §1 · p. 2
Our Contribution
- RG generalizes Robust Matching with parameter α: α=t recovers RM, while α<t favors assignments to nearest available servers.Its second parameter lets RG favor greedy assignments while retaining an auxiliary offline matching.Source: §1 · p. 3
- RG’s competitive ratio is at most 6.6604k−2.89, independent of total capacity n, improving on the previous best-known 8k−7 bound.The introduction also gives a simpler (20/3)k−3 analysis before the tighter analysis.Source: §1 · p. 3
- For every fixed t > 1 and 1 ≤ α ≤ t, RG has a competitive-ratio result and recovers RM’s metric-sensitive guarantees.Comparable metric-sensitive guarantees are not known for the cited transportation algorithms of Harada and Itoh or Arndt et al.Source: §1 · pp. 2–3
- With suitable parameters, RG has an O(k) competitive guarantee and a guaranteed greedy-cost fraction that approaches one-half as t increases.The stated fraction result applies when α=o(t).Source: §1 · p. 3
Experiments
- Experiments on real-world datasets report that RG improves over Greedy by up to 15.02% on correlated arrivals and outperforms Arndt et al.’s algorithm while retaining many nearest-neighbor assignments.On natural arrival orders, RG retains Greedy’s strong performance.Source: §1 · p. 3
2 Robustified Greedy Algorithm
Robustified Greedy chooses a minimum-net-cost augmenting path using an online matching and an auxiliary offline matching. Its parameters favor nearest-server assignments, while non-greedy choices are tied to reducing accumulated auxiliary-matching cost.
2 Robustified Greedy Algorithm
- For each new request, RG selects a minimum-(t, α)-net-cost augmenting path and makes the corresponding online assignment while augmenting its offline matching.The online and offline matchings retain the same server loads and free servers after each arrival.Source: §2 · p. 4
- Setting α=t recovers Robust Matching, whereas α<t discounts direct paths and favors nearest-server assignments.A selected direct path goes to a nearest free server and yields a greedy assignment.Source: §2 · p. 4
- The online cost over a sequence is bounded using the selected paths’ net-costs and the total weight G of greedy edges.The cost-accounting lemma is used both to explain decisions and to analyze the competitive ratio.Source: §2 · pp. 4–5
2.1 Greedy Assignment Fraction
- When 1≤α<(t−1)/2, every non-greedy choice reduces the offline matching cost, and the greedy-edge cost fraction approaches one-half for fixed α or α=o(t).For α=t, the same argument gives no positive lower bound on G.Source: §2.1 · pp. 5–6
3 Primal-Dual Implementation
The primal-dual implementation searches a residual graph for a minimum-net-cost augmenting path, updates dual weights, and augments both matchings. Feasibility and structural properties of the maintained matching support the analysis.
3.1 Processing a request via primal-dual algorithm
- For each arrival, the implementation searches from the new request to a free server, updates dual weights, then assigns the request and augments the offline matching along the selected path.The matching and dual weights are maintained as (t, α)-feasible.Source: §3 · p. 6, §3.1 · p. 7
3 Primal-Dual Implementation
- RG processes each request in O(nk log n) time, dominated by Dijkstra’s search on a residual graph with O(nk) edges.The dual updates and matching augmentation each take O(n) time.Source: §3.1 · p. 7
3.1 Processing a request via primal-dual algorithm
- The dual update preserves (t, α)-feasibility, and every residual edge on the selected path has zero slack immediately before augmentation.The selected path has minimum (t, α)-net-cost.Source: §3.1 · pp. 7, 9
3.2 Properties used in the analysis
- For α>1, every positive-weight edge inserted by a direct augmenting path remains in the offline matching until its server saturates.The result supplies persistent structure used in the subsequent analysis.Source: §3.2 · p. 9
4 Competitive ratio
The competitive analysis partitions arrivals into server-saturation epochs and bounds their costs using nearest-free-server distances, selected-path costs, and matching structure. It first establishes a simpler guarantee, then tightens the analysis by optimizing parameters.
4 Competitive ratio
- For t=4 and α=2, the epoch analysis establishes a competitive ratio of at most 20k/3−3.The section identifies this as its initial competitive-ratio bound.Source: §4 · p. 10
- Each saturation epoch ends when a server uses its last capacity unit; servers free at the epoch’s start remain free until its final arrival.There are at most k epochs, one per server saturation.Source: §4 · p. 10
4.1 Tighter Analysis Using Parameter Optimization
- The tighter analysis chooses α=√t so the offline-matching terms telescope across epochs, and its parameter choice proves Theorem 1.The text reports that this yields an O(k) guarantee for the broader parameter range.Source: §4.1 · pp. 12–13
- Within an epoch, the analysis bounds total nearest-free-server distances and selected-path costs using OPT and the offline matching’s weight at the epoch’s start.These bounds feed the epoch cost accounting.Source: §4 · p. 11, §4.1 · p. 13
5 Competitive Analysis for the RM Algorithm
The section proves that RM is competitive for online metric transportation by analyzing it through RG’s saturation-epoch framework at α=t.
5 Competitive Analysis for the RM Algorithm
- RM is competitive for online metric transportation.The section treats RM as RG’s special case with α=t and retains the saturation epochs.Source: §5 · p. 13
- Setting α=t removes the greedy-cost term from Lemma 4’s bound on online cost within each saturation epoch.The proof uses a direct path to a nearest free server as a candidate of net cost t d_i.Source: §5 · pp. 13–14
6 Input-sensitive guarantee
The section derives an input-sensitive guarantee from server-location geometry, with Euclidean locations yielding μ_X(S)=O_d(k^(1−1/d)) for d>1.
6 Input-sensitive guarantee
- For d-dimensional Euclidean server locations with d>1, μ_X(S)=O_d(k^(1−1/d)), yielding Theorem 2’s competitive ratio.The section defines its geometric measure using the tour length and diameter of server subsets.Source: §6 · p. 14
6.1 Algorithmic facts used by the geometric argument
- The geometric argument uses an online-cost-from-net-cost bound and free-server separation; RG’s discounted free-free edges make the latter’s denominator α rather than RM’s t.The online matching weight is bounded in terms of the total net cost Φ.Source: §6.1 · pp. 15–16
6.2 Dyadic net-cost groups
- The proof partitions requests into dyadic net-cost groups and bounds the number of groups logarithmically for fixed t and α.Both group counts m and L are O(log(2n)) for fixed parameters.Source: §6.2 · p. 16, §6.6 · p. 22
6.3 Clusters and optimal paths
- Requests are clustered around centers, and each cluster request gets an optimal alternating path ending at a free server; these paths are edge-disjoint.The terminal server is free with respect to the matching before the cluster center arrives.Source: §6.3 · p. 17
6.4 Outer groups and weighted balls
- Outer groups organize net-cost requests by scale; distinct centers have distinct optimal server locations, giving tour edges length at least r_j.Source: §6.4 · p. 19
6.5 Weighted Vitali selection
- A maximum-weight Vitali selection produces pairwise-disjoint balls, while intersecting sets partition the originals and lie inside selected balls’ threefold expansions.Source: §6.5 · p. 20
6.6 Completing the proof
- For fixed t and α, m and L are O(log(2n)); summing the groups yields the final bound, absorbing the additive 16α+1 term when the server set has positive diameter.When all server locations coincide, the theorem is immediate because every feasible assignment has the same cost.Source: §6.6 · pp. 21–22
7 Experiments
Across the tested datasets, RG stays close to Greedy on NYC timestamp traces and improves on Greedy under directional ordering and on MovieLens. RG uses more computation than online baselines, while most decisions remain nearest-server assignments.
Setup
- The evaluation averages ten instances of 10,000 requests and uses NYC timestamp and directional orders plus directional MovieLens arrivals.NYC’s directional order sorts the same requests by y-coordinate; MovieLens online algorithms use a 12-dimensional projection, with assignments and OPT evaluated in 100 dimensions.Source: §7 · p. 22
Assignment cost
- RG reduces NYC directional-trace cost relative to Greedy by 10.75% to 15.02% as α rises from 1 to 2, and by 8.54% to 15.02% as k rises from 50 to 500.On MovieLens, RG costs less than Greedy in all ten repetitions, with mean reductions of 0.41% to 0.51%; both methods outperform Arndt et al.Source: §7 · p. 23, Figure 1 · p. 23
- On NYC timestamp traces, RG stays within 0.5% of Greedy for every tested α, while both cost about 31% less than Arndt et al.RM costs 1.0% more than Greedy on these traces.Source: §7 · p. 23
Runtime trade-off
- RG and RM require more computation than the two online baselines, but remain substantially faster than exact offline optimization.Nearest-server assignments constitute 97.37–98.05% of RG’s NYC decisions and 51.79–63.76% of its MovieLens decisions.Source: §7 · p. 24
8 Conclusion
Robustified Greedy combines nearest-neighbor decisions with Robust Matching’s robust corrections and improves the competitive guarantee for online transportation. Its analysis links positive-cost greedy edges to server saturation and accounts for cost over saturation epochs.
Conclusion
- RG interpolates between nearest-neighbor decisions and Robust Matching’s robust augmenting-path corrections.The analysis identifies positive-cost greedy edges persisting until their servers saturate, allowing cost accounting over saturation epochs.Source: §8 · p. 24
- RG achieves a competitive ratio of 6.6604k−2.89, independent of total capacity, while preserving an O(k^(1−1/d) log^2 n) guarantee in fixed-dimensional Euclidean spaces.The framework also yields an O(k) guarantee for Robust Matching.Source: §8 · p. 24
- Future work includes narrowing the gap to the (2k−1) lower bound and determining whether metric-sensitive logarithmic factors can be reduced.Source: §8 · p. 24
AI use statement
The authors disclose using generative AI tools to formulate and prove mathematical claims, implement methods, and provide feedback on experiments; they reviewed the AI-assisted work and take responsibility for the final content.
AI use statement
- The authors report AI assistance with mathematical claims and proofs, method implementation, and experiment feedback, while taking responsibility for the final content.Source: AI use statement · p. 24
D Additional Experimental Results
The appendix reports complete parameter sweeps of mean cumulative assignment cost on NYC and MovieLens, with settings and evaluation procedures matching Section 7.
D Additional Experimental Results
- All sweeps use the settings, instances, and evaluation procedures from Section 7.Source: D Additional Experimental Results · p. 27
- Figure 2 sweeps α across NYC timestamp and directional arrival orders, reporting mean cumulative assignment cost over ten instances.The two rows correspond to the two arrival orders.Source: Figure 2 · p. 27
- Figure 3 varies k on NYC’s directional order and reports mean cumulative assignment cost over ten instances.Source: Figure 3 · p. 27
- Figure 4 sweeps α on MovieLens at t = 1.12, reporting mean cumulative assignment cost over ten instances.Source: Figure 4 · p. 28
- Figure 5 sweeps α on MovieLens at t = 6, reporting mean cumulative assignment cost over ten instances.Source: Figure 5 · p. 28