Greedy Oriented Flows
Greedy Oriented Flows
复制标题
贪婪导向流
DOI：
10.1007/s00453-017-0306-4
复制
发表时间：
2017
期刊：
影响因子：
1.1
通讯作者：
Britta Peis
中科院分区：
文献类型：
--
作者：
Ulrich Faigle;Walter Kern;Britta Peis
我们研究了以下贪婪的方法来攻击线性规划的类型，其中A有条目：贪婪算法从一个可行的solutionx开始，迭代地，选择一个改进的变量，并提高它，直到一些约束变得紧密。在特殊情况下，其中A是某个有向图的边路关联矩阵，并且，该贪婪算法对应于求解Gw.r.t.中的最大（s，t）流问题的Ford-Fulkerson算法。边缘电容众所周知，Ford-Fulkerson算法总是以最优流终止，并且增广的数量强烈地依赖于每次迭代中路径的选择。Edmonds-Karp规则偏好具有较少弧的路径，这导致运行时间至多增加。本文研究了一般类型的矩阵A和偏好规则的变量，使贪婪算法的有效性。在本文中，我们确定的条件，保证贪婪算法不循环，和/或贪婪算法的最优性，和/或产生一个二次（行数）的扩增。我们说明了我们的方法与流动和循环问题，定期定向拟阵。
We investigate the following greedy approach to attack linear programs of typewhereAhas entries in: The greedy algorithm starts with a feasible solutionxand, iteratively, chooses an improving variable and raises it until some constraint becomes tight. In the special case, whereAis the edge-path incidence matrix of some digraph, and, this greedy algorithm corresponds to the Ford–Fulkerson algorithm to solve themax (s,t)-flow probleminGw.r.t. edge-capacitiesu. It is well-known that the Ford–Fulkerson algorithm always terminates with an optimal flow, and that the number of augmentations strongly depends on the choice of paths in each iteration. The Edmonds–Karp rule that prefers paths with fewer arcs leads to a running time of at mostaugmentations. The paper investigates general types of matricesAand preference rules on the variables that make the greedy algorithm efficient. In this paper, we identify conditions that guarantee for the greedy algorithm not to cycle, and/or optimality of the greedy algorithm, and/or to yield a quadratic (in the number of rows) number of augmentations. We illustrate our approach with flow and circulation problems on regular oriented matroids.
登录
查看更多内容
正则拟阵中的代数流
DOI：
10.1016/0166-218x(80)90052-9
发表时间：
1980
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
H. Hamacher
通讯作者：
H. Hamacher
某些类别的组合线性规划的两阶段贪婪算法
DOI：
--
发表时间：
2008
期刊：
TALG
影响因子：
--
作者：
U. Faigle;Britta Peis
通讯作者：
Britta Peis
存在非理性问题数据时“增广路径”算法的有限终止
DOI：
--
发表时间：
2006
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
B. C. Dean;M. Goemans;Nicole Immorlica
通讯作者：
Nicole Immorlica
常规拟阵中的最小成本流
影响因子：
2.7
作者：
R. Burkard;H. Hamacher
通讯作者：
H. Hamacher
子模块系统的主要结构
影响因子：
1.1
作者：
S. Fujishige
通讯作者：
S. Fujishige