The Online Transportation Problem

DOI10.1137/S0895480198342310MaRDI QIDQ4490792zbMATH OpenOpenAlexFDO

Authors Bala Kalyanasundaram, Kirk Pruhs

Publication date 20 July 2000

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480198342310

zbMATH Keywords

online algorithmsmatchingcompetitive analysis

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Transversal (matching) theory (05D15)

Recommendations

• The online transportation problem
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• On-line load balancing
• On-line \(k\)-truck problem and its competitive algorithms.
• A competitive 2-server algorithm

Cited in

(18)

• Online Vehicle Routing Problems: A Survey
• Online bottleneck matching
• Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
• Online facility assignment for general layout of servers on a line
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• Online bottleneck matching on a line
• On the refinement of liveness properties of distributed systems
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• Capacity-insensitive algorithms for online facility assignment problems on a line
• Serve or skip: the power of rejection in online bottleneck matching
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• The online transportation problem
• Online bottleneck semi-matching
• An optimal deterministic algorithm for online \(b\)-matching
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

This page was built for publication: The Online Transportation Problem

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