Stronger bounds and faster algorithms for packing in generalized kernel systems

DOI10.1007/S10107-015-0948-4MaRDI QIDQ312660zbMATH OpenOpenAlexFDO

Authors Mario Leston-Rey, Orlando Lee

Publication date 16 September 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-015-0948-4

zbMATH Keywords

algorithmgeneralized kernel systempackingupper bound

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Combinatorial optimization (90C27) Numerical analysis (educational aspects) (97N40)

Review text

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.

Recommendations

• Kernels for Packing and Covering Problems
• Kernelization of packing problems
• An improved kernelization for \(P_{2}\)-packing
• An improved kernelization algorithm for \(r\)-set packing
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• Kernels for packing and covering problems
• Kernelization algorithms for packing problems allowing overlaps
• Explicit linear kernels for packing problems
• Kernelization for \(P_2\)-packing: a gerrymandering approach
• A Problem Kernelization for Graph Packing

Cites work

• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A faster algorithm for packing branchings in digraphs
• A note on disjoint arborescences
• An integer analogue of Carathéodory's theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Directed cut transversal packing for source-sink connected graphs
• Fractional packing in ideal clutters
• Fractional Packing ofT-Joins
• scientific article; zbMATH DE number 5764894 (Why is no real title available?)
• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• scientific article; zbMATH DE number 634030 (Why is no real title available?)
• Improved bound for the Carathéodory rank of the bases of a matroid
• Increasing the rooted connectivity of a digraph by one
• Integral packing of branchings in capacitaded digraphs
• Min-max Relations for Directed Graphs
• On covering intersecting set-systems by digraphs
• On two minimax theorems in graph
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing arborescences
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• Polyhedra with the integer Carathéodory property
• Rooted \(k\)-connections in digraphs
• Variations for Lovász’ Submodular Ideas

Cited in

(5)

• Kernels for packing and covering problems
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• Kernels for Packing and Covering Problems
• An improved kernelization algorithm for \(r\)-set packing
• An improved kernelization for \(P_{2}\)-packing

This page was built for publication: Stronger bounds and faster algorithms for packing in generalized kernel systems

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