Relationship of two formulations for shortest bibranchings
Relationship of two formulations for shortest bibranchings
复制标题
最短双支化的两种公式的关系
DOI：
10.1007/s13160-020-00432-0
复制
发表时间：
2020
影响因子：
0.9
通讯作者：
K. Takazawa
中科院分区：
文献类型：
--
作者：
K. Murota;K. Takazawa
最短双分支问题是二部图中的最小权边覆盖问题和有向图中的最小权树形问题的一般推广。对于最短的双分支问题，Keijlane和Pendavingh给出了一种有效的原始-对偶算法（J ComB Theory Ser B 73：130-145，1998），并且该问题的易处理性归因于Schrijver（Ann Discret Math 16：261-280，1982）的线性规划公式中的完全对偶完整性。关于该问题的易处理性的另一观点由Takazawa的赋值拟阵交集公式化（Jpn J Ind Appl Math 29：561-573，2012）提供。在本文中，我们讨论了这两个公式之间的关系最短双分支问题。我们首先证明了赋值拟阵交公式可以通过Benders分解从线性规划公式导出，其中在分解过程中保持完整性，并且所得凸规划具有离散凸性。然后，我们将展示如何从另一个配方的一对原始和对偶最优解的构造，从而提供了多面体组合和离散凸分析之间的连接。
The shortest bibranching problem is a common generalization of the minimum-weight edge cover problem in bipartite graphs and the minimum-weight arborescence problem in directed graphs. For the shortest bibranching problem, an efficient primal-dual algorithm is given by Keijsper and Pendavingh (J Comb Theory Ser B 73:130–145, 1998), and the tractability of the problem is ascribed to total dual integrality in a linear programming formulation by Schrijver (Ann Discret Math 16:261–280, 1982). Another view on the tractability of this problem is afforded by a valuated matroid intersection formulation by Takazawa (Jpn J Ind Appl Math 29:561–573, 2012). In the present paper, we discuss the relationship between these two formulations for the shortest bibranching problem. We first demonstrate that the valuated matroid intersection formulation can be derived from the linear programming formulation through the Benders decomposition, where integrality is preserved in the decomposition process and the resulting convex programming is endowed with discrete convexity. We then show how a pair of primal and dual optimal solutions of one formulation is constructed from that of the other formulation, thereby providing a connection between polyhedral combinatorics and discrete convex analysis.
登录
查看更多内容
匹配森林约束的总对偶完整性
影响因子：
1.1
作者：
A. Schrijver
通讯作者：
A. Schrijver
影响因子：
1.1
作者：
M. Babenko
通讯作者：
M. Babenko
影响因子：
0.8
作者：
Murota, K
通讯作者：
Murota, K
最短分枝和有价值的拟阵交集
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
奥野緑;梅田貴士;前原俊信;Henmi Masayuki;K. Takazawa
通讯作者：
K. Takazawa
K.Kurota：“评估拟阵交集 I：最优标准”SIAM J.Discrete Math.9。
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--