.png){kind=icon}
.png){kind=icon}
Return
A strongly polynomial Contraction-Expansion algorithm for network flow problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2017.02.019.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper addresses the solution of the capacitated minimum cost flow problem on a network containing n nodes and m arcs. Satisfying necessary and sufficient optimality conditions can be done on the residual network although it can be quite time consuming as testified by the minimum mean cycle canceling algorithm (MMCC). We introduce a contracted network which exploits these conditions on a much smaller network. Since the construction of this contracted network is very flexible, we study its properties depending on the construction choice. A generic contraction algorithm is then produced around the contracted network. Interestingly enough, it turns out it encapsulates both the MMCC and primal network simplex algorithms as extreme cases. By guiding the solution using a particular expansion scheme, we are able to recuperate theoretical results from MMCC. As such, we obtain a strongly polynomial Contraction-Expansion algorithm which runs in O(m(3)n(2)) time. There is thus no improvement of the runtime complexity, yet the expansion scheme sticks to very practical observations of MMCC's behavior, namely that of phases and jumps on the optimality parameter. The solution time is ultimately significantly reduced, even more so as the size of the instance increases. (C) 2017 Elsevier Ltd. All rights reserved.
Keywords:
Network flow problem
Residual network
Contracted network
Minimum mean cost cycle
Complexity analysis
Strongly polynomial algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W