.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Network flow problem
Residual network
Contracted network
Minimum mean cost cycle
Complexity analysis
Strongly polynomial algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
分享收藏A Structurally Variant Form of the 2B4 Antigen Is Expressed on the Cell Surface of Mouse Mast Cells
OAAI
OAAI分享收藏Tight bounds on the number of minimum-mean cycle cancellations and related results.png)
Algorithmica
AlgorithmicaIF0
PREAI
分享收藏Rocking Motion of a Mid-Rise Steel Plate Shear Wall on Foundation–Soil Medium中高层钢板的剪切墙在基础-土壤介质中的摇摆运动
PREAI
分享收藏 没有更多内容
没有更多内容