An approximation algorithm for discrete minimum cost flows over time problem. (1st January 2014)

• Record Type: Journal Article
• Authors: Rostami, Reza; Ebrahimnejad, Ali
• Is Part Of: International journal of operational research. Volume 20:Number 2(2014)
• Page Start: 226
• Page End: 239
• Publication Date: 2014-01-01
• Subjects: minimum cost flow problem -- flows over time -- approximation algorithm -- operational research; Operations research -- Periodicals; 003.05
• Languages: English
• ISSNs: 1745-7645

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.