Title: An approximation algorithm for discrete minimum cost flows over time problem

Authors: Reza Rostami; Ali Ebrahimnejad

Addresses: Mathematics Department, Islamic Azad University, Parand Branch, P.O. Box 3761835884, Robatkarim, Tehran, Iran ' Mathematics Department, Islamic Azad University, Qaemshahr Branch, P.O. Box 163, Qaemshahr, Iran

Abstract: Ford and Fulkerson around 50 years ago introduced flows over time by adding time dimension to the traditional network flow model. Road and air traffic control, production systems, communication networks (e.g., the internet) and financial flows are examples of this subject. What distinguishes flows over time from the traditional model is transit time on every arc which specifies the amount of time, flow units need to traverse the arc. In this model, flow rate entering an arc may change over time. One of the problems arising in this issue is the minimum cost flow over time problem which aims to determine an s-t flow over time f that satisfies demand d within given time horizon T at minimum cost. It is already shown that this problem is NP-hard, thus as usual a fair amount of study devoted to finding an efficient approximation algorithm for this issue. In this paper, we introduce an approximation algorithm for the T-length bounded discrete minimum cost flows over time problem.

Keywords: minimum cost flow problem; flows over time; approximation algorithm; operational research; network flow models; modelling.

DOI: 10.1504/IJOR.2014.061773

International Journal of Operational Research, 2014 Vol.20 No.2, pp.226 - 239

Received: 19 Oct 2012
Accepted: 23 Nov 2012
Published online: 21 Jun 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article