A nearly optimal deterministic algorithm for online transportation problem

DOI10.4230/LIPICS.ICALP.2025.94MaRDI QIDQ7363182zbMATH OpenFDO

Authors Tsubasa Harada, Toshiya Itoh

Publication date 29 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.94

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A collection of lower bounds for online matching on the line
• A randomized algorithm for online metric b-matching
• A robust and optimal online algorithm for minimum metric bipartite matching
• An input sensitive online algorithm for the metric bipartite matching problem
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Approximation and Online Algorithms
• Capacity-insensitive algorithms for online facility assignment problems on a line
• scientific article; zbMATH DE number 7236471 (Why is no real title available?)
• Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
• On-line algorithms for weighted bipartite matching and stable marriages
• Online facility assignment
• Online facility assignment for general layout of servers on a line
• Online Weighted Matching
• Randomized online algorithms for minimum metric bipartite matching
• Stochastic online metric matching
• The Online Metric Matching Problem for Doubling Metrics
• The Online Transportation Problem
• The Online Transportation Problem: On the Exponential Boost of One Extra Server

This page was built for publication: A nearly optimal deterministic algorithm for online transportation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363182)