The Online Transportation Problem: On the Exponential Boost of One Extra Server

DOI10.1007/978-3-540-78773-0_20MaRDI QIDQ5458531zbMATHOpenAlexFDO

Authors Christine Chung, Patchrawat Uthaisombut, Kirk Pruhs

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://digitalcommons.conncoll.edu/cgi/viewcontent.cgi?article=1008&context=comscifacpub

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• The Online Transportation Problem
• The online transportation problem
• Online k-Server Routing Problems
• Online \(k\)-server routing problems
• A polylogarithmic-competitive algorithm for the \(k\)-server problem

Cited in

(11)

• Online bottleneck matching
• scientific article; zbMATH DE number 7204578 (Why is no real title available?)
• The Online Transportation Problem
• Online facility assignment for general layout of servers on a line
• Serve or skip: the power of rejection in online bottleneck matching
• The online transportation problem
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching

This page was built for publication: The Online Transportation Problem: On the Exponential Boost of One Extra Server

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