Relationship of two formulations for shortest bibranchings

DOI10.1007/S13160-020-00432-0zbMATH Open1467.05094arXiv1706.02029OpenAlexW3045463995MaRDI QIDQ2024606FDOQ2024606

Kenjiro Takazawa, Kazuo Murota

Publication date: 4 May 2021

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Abstract: 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 (1998), and the tractability of the problem is ascribed to total dual integrality in a linear programming formulation by Schrijver (1982). Another view on the tractability of this problem is afforded by a valuated matroid intersection formulation by Takazawa (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.

Full work available at URL: https://arxiv.org/abs/1706.02029

zbMATH Keywords

dualitypolyhedral combinatoricsBenders decompositionintegralitydiscrete convex analysis

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Combinatorial optimization (90C27) Signed and weighted graphs (05C22)

Cites Work

• Discrete Convex Analysis
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Introduction to Stochastic Programming
• Optimum branchings
• Min-max Relations for Directed Graphs
• Linear Programming
• \(M\)-convex function on generalized polymatroid
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• Total dual integrality of matching forest constraints
• An efficient algorithm for minimum-weight bibranching
• An efficient scaling algorithm for the minimum weight bibranching problem
• Submodular flow problem with a nonseparable cost function
• Optimal Matching Forests and Valuated Delta-Matroids
• Optimal Matching Forests and Valuated Delta-Matroids
• Shortest bibranchings and valuated matroid intersection

Cited In (2)

• Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs
• The b‐bibranching problem: TDI system, packing, and discrete convexity

This page was built for publication: Relationship of two formulations for shortest bibranchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2024606)