Stronger bounds and faster algorithms for packing in generalized kernel systems

Autor: Orlando Lee, Mario Leston-Rey
Rok vydání: 2015
Předmět:
Zdroj: Mathematical Programming. 159:31-80
ISSN: 1436-4646
0025-5610
DOI: 10.1007/s10107-015-0948-4
Popis: 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; $$m-n+2$$m-n+2 for the size of a packing of spanning arborescences; $$m+r-1$$m+r-1 for the size of a packing of spanning branchings; $$m+r-1$$m+r-1 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 $$m+r-1$$m+r-1 for the size of a packing in Frank's bi-set systems with the mixed intersection property. Next, we consider the framework of uncrossinggksmf. 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 Berczi and Frank.
Databáze: OpenAIRE
Externí odkaz: