Stronger bounds and faster algorithms for packing in generalized kernel systems

• 成果类型: Article
• 署名作者: Leston-Rey, Mario; Lee, Orlando
• 署名单位: Universidade Estadual de Campinas
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0948-4
• 发表日期: 2016
• 页码: 31-80
• 关键词: digraphs; graphs; arborescences; branchings; cut

摘要

In this paper, we consider integral (and fractional) packing problems in generalized kernel systems with a mixed family (gksmf). This framework generalizes combinatorial packing problems of several structures as, for instance, st-flows, arborescences, kernel systems, branchings, convex branchings, and covers in bi-set systems. We provide an algorithm, which improves by a factor of 2 on the upperbound for the size of a packing in a gksmf, provided by Leston-Rey and Wakabayashi. This in turn implies the following upperbounds, where n is the number of vertices, m the number of arcs, and r the number of root-sets of a digraph: m for the size of a packing of st-paths; for the size of a packing of spanning arborescences; for the size of a packing of spanning branchings; for the size of a packing of Fujishige's convex branchings; m for the size of a packing of dijoins of a restricted form; and for the size of a packing in Frank's bi-set systems with the mixed intersection property. Next, we consider the framework of uncrossing gksmf. We describe an algorithm for computing a packing in such a framework with the same upperbound guarantee. The time complexity of this algorithm implies an improvement over the best time complexity bounds known for computing a packing of spanning arborescences of Gabow and Manu, for computing a packing of spanning branchings of Lee and Leston-Rey, and for computing a packing of covers in a bi-set system with the mixed intersection property of B,rczi and Frank.