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

DOI10.1016/J.ORL.2014.12.008zbMATH Open1408.90049arXiv1406.4799OpenAlexW2088456596MaRDI QIDQ1785329FDOQ1785329

Authors: Martin Groß, Martin Skutella 

Publication date: 28 September 2018

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

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$.

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

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

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)

Cites Work

• The quickest flow problem
• Constructing maximal dynamic flows from static flows
• An introduction to network flows over time
• Title not available (Why is that?)
• Multicommodity flows over time: Efficient algorithms and complexity
• Quickest Flows Over Time
• 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)