Stronger bounds and faster algorithms for packing in generalized kernel systems (Q312660): Difference between revisions

The paper investigates packing problems in generalized kernel systems with a mixed family (gksmf). These problems generalize many combinatorial packing problems such as \(st\)-flows, arborescences and branchings. The results concern better upper bounds on the size of a packing and improved oracle polynomial-time algorithms for finding packings. It is shown that an integral gksmf is feasible if and only if it has an integral packing. Using a series of further results, the authors provide an algorithm that improves by a factor of 2 an earlier upper bound from the literature for packing in a gksmf. Finally, for the more constrained framework of uncrossing gksmf, they provide an algorithm, which improves the time complexity of known algorithms for several special cases.