The Quickest Multicommodity Flow Problem

摘要: Traditionally, flows over time are solved in time-expanded networks which contain one copy of the original network for each discrete step. While this method makes available whole algorithmic toolbox developed static flows, its main and often fatal drawback is enormous size network. In particular, approach usually does not lead to efficient algorithms with running polynomial input since only pseudo-polynomial.We present two different approaches coping difficulty. Firstly, inspired by work Ford Fulkerson on maximal s-t-flows (or 'maximal dynamic s-t-flows'), we show that static, lengthbounded provably good multicommodity time.These solutions feature a simple structure but can also be computed very efficiently time.Secondly, investigate 'condensed' rely rougher discretization time. Unfortunately, there natural tradeoff between roughness quality achievable solutions. However, prove solution arbitrary precision through an appropriate leading condensed expanded size. yields fully approximation scheme quickest flow problem more general problems.