.png){kind=icon}
.png){kind=icon}
Return
Time-Dependent Minimum Cost Dynamic Flow Problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s40305-025-00620-0.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we study a minimum cost flow problem on a dynamic network in a discrete-time model, which is known to be NP-hard. All attributes in this network, including capacities, storage capacities, costs, storage costs, and supply or demand at any node, are time-dependent. First, we prove that the existence of a feasible dynamic flow is equivalent to solving a time-dependent maximum dynamic flow problem, and we provide a pseudopolynomial-time exact algorithm for this feasibility problem with computational complexity of O((m+n)n2T3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}((m+n)n<^>{2}T<^>{3})$$\end{document}, where m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m$$\end{document} and n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} are the number of arcs and nodes in the network, respectively, and T\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T$$\end{document} is a given time horizon. Next, based on a feasible dynamic flow, we present an extended cost scaling algorithm that correctly computes a time-dependent minimum cost dynamic flow in O((m+n)n2T3log(nCT))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}((m+n)n<^>{2}T<^>{3}\log (nCT))$$\end{document} time, where C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C$$\end{document} represents the maximum absolute value of all costs in the network.
Keywords:
Time-dependent
Minimum cost dynamic flow
Maximum dynamic flow
Pseudopolynomial-time algorithm
Cost scaling
Journal
J
IF:
1.1
Papers:
64
Citations:
487
Organization
No organization information available