An approximation algorithm for discrete minimum cost flows over time problem

摘要

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.