A tight bound on the speed-up through storage for quickest multi-commodity flows

DOI10.1016/J.ORL.2014.12.008MaRDI QIDQ1785329zbMATH OpenOpenAlexFDO

Authors Martin Groß, Martin Skutella

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.4799

zbMATH Keywords

storagemulti-commodityquickest flowflow over timedynamic flowwaiting

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Transportation, logistics and supply chain management (90B06)

Abstract: Multi-commodity flows over time exhibit the non-intuitive property that letting flow wait can allow us to send flow faster overall. Fleischer and Skutella (IPCO~2002) show that the speed-up through storage is at most a factor of~$2$, and that there are instances where the speed-up is as large as a factor of~$4/3$. We close this gap by presenting a family of instances for which the speed-up factor through storage converges to~$2$.

Recommendations

• Quickest Flows Over Time
• Maximum multicommodity flows over time without intermediate storage
• scientific article; zbMATH DE number 2086912
• scientific article; zbMATH DE number 2079322
• An FPTAS for quickest multicommodity flows with inflow-dependent transit times

Cites work

• scientific article; zbMATH DE number 2086912 (Why is no real title available?)
• An introduction to network flows over time
• Constructing maximal dynamic flows from static flows
• Multicommodity flows over time: Efficient algorithms and complexity
• Quickest Flows Over Time
• The quickest flow problem
• Traffic Networks and Flows over Time
• Universal packet routing with arbitrary bandwidths and transit times

Cited in

(1)

• Macroscopic evacuation plans for natural disasters. A lexicographical approach for duration and safety criteria: \(\mathrm{Lex}((Q|S)\mathrm{Flow})\)

This page was built for publication: A tight bound on the speed-up through storage for quickest multi-commodity flows

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