.png){kind=icon}
Return
Time-varying minimum cost flow problems
.png){kind=icon}
PRE
AI
DOI：10.1016/S0377-2217(00)00059-X.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 time-varying network. Let N(V, A, l, b, c(r), c(w)) be a network with an are set A and a vertex set V. Each a is an element of A is associated with three integer parameters: a positive transit time b(a, t), an arbitrary transit cost c(r)(a, t), and a positive capacity limit l(a, t). Each x is an element of V is associated with two integer parameters: a waiting cost c(w)(x, t) and a vertex capacity l(x, t). All these parameters are functions of the discrete time t = 0, 1, 2,... The objective is to find an optimal schedule to send a flow from the origin (the source vertex) to its destination (the sink vertex) with the minimum cost, subject to the constraint that the flow must arrive at the destination before a deadline T. Three versions of the problem are examined, which are classified depending on whether waiting at the intermediate vertices of the network is strictly prohibited, arbitrarily allowed, or bounded. Three algorithms with pseudopolynomial time complexity are proposed, which can find optimal solutions to the three versions of the problem, respectively. (C) 2001 Elsevier Science B.V. All rights reserved.
Keywords:
time-varying network
minimum cost flow
dynamic programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveDo Nurse-Led Skill Training Interventions Affect Informal Caregivers' Out-of-Pocket Expenditures?
OAAI
OAAIShareSaveShareSaveShareSaveShareSave no more
no more