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

作者：Gross Martin^*; Skutella Martin

来源：Operations Research Letters, 2015, 43(1): 93-95.

DOI：10.1016/j.orl.2014.12.008

• Dynamic flow
• Flow over time
• Quickest flow
• Multi-commodity
• Storage
• Waiting

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.

• 出版日期2015-1