Combinatorial optimization. Packing and covering
From MaRDI portal
This nice survey presents new and elegant proofs of classical results for the integer programming models known as set packing and covering. There are min-max, polyhedral, exclude minor, and decomposition results. We give the headings of the 10 chapters: 1. Clutters, 2. \(T\)-Cuts and \(T\)-Joins, 3. Perfect Graphs and Matrices, 4. Ideal Matrices, 5. Odd Cycles in Graphs, 6. \(0,\pm 1\) Matrices and Integral Polyhedra, 7. Signing 0,1 Matrices to Be Totally Unimodular or Balanced, 8. Decomposition by \(k\)-Sum, 9. Decomposition of Balanced Matrices, 10. Decomposition of Perfect Graphs. For each of 18 conjectures, stated in the book, the author offers \$ 5000 for the first paper solving or refuting it.
Recommendations
Cited in
(only showing first 100 items - show all)- Blowup algebras of square-free monomial ideals and some links to combinatorial optimization problems
- On the set covering polyhedron of circulant matrices
- Lehman matrices
- A superclass of edge-path-tree graphs with few cliques
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Packing odd circuits in Eulerian graphs
- An approach to solving \(A^{k}=J-I\)
- Square-free perfect graphs.
- Random monomial ideals
- Packing arborescences in random digraphs
- A tight lower bound for the hardness of clutters
- Non total-unimodularity neutralized simplicial complexes
- On total \(f\)-domination: polyhedral and algorithmic results
- Progress on the description of identifying code polyhedra for some families of split graphs
- Route relaxations on GPU for vehicle routing problems
- Polyhedra associated with identifying codes in graphs
- One-overlapped factorizations of non-abelian groups
- Perfectness of clustered graphs
- A characterization of weakly bipartite graphs
- The facets and the symmetries of the approval-voting polytope
- Cuboids, a class of clutters
- Depth and regularity of monomial ideals via polarization and combinatorial optimization
- Pitch, extension complexity, and covering problems
- The star dichromatic number
- Rees algebras of filtrations of covering polyhedra and integral closure of powers of monomial ideals
- Colouring non-even digraphs
- Normality criteria for monomial ideals
- A duality theorem for the ic-resurgence of edge ideals
- On partial descriptions of König graphs for odd paths and all their spanning supergraphs
- Idealness of \(k\)-wise intersecting families
- Total dual dyadicness and dyadic generating sets
- Shattering inequalities for learning optimal decision trees
- Binary signed-graphic matroids: representations and recognition algorithms
- Sparse recovery with integrality constraints
- On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
- The max-flow min-cut property and \(\pm 1\)-resistant sets
- Recognizing Helly edge-path-tree graphs and their clique graphs
- Idealness and 2-resistant sets
- Structure of cubic Lehman matrices
- Alternatives for testing total dual integrality
- Balanced matrices
- The Steiner connectivity problem
- On asteroidal sets in chordal graphs
- The maximum vertex coverage problem on bipartite graphs
- A new approach for modeling and solving set packing problems
- Solution of three problems of Cornuéjols
- Relative blocking in posets
- The max-flow min-cut property of two-dimensional affine convex geometries
- Cohen-Macaulay, shellable and unmixed clutters with a perfect matching of König type
- Some insight into characterizations of minimally nonideal matrices
- Clutter nonidealness
- Note on: N. E. Aguilera, M. S. Escalante, G. L. Nasini, ``The disjunctive procedure and blocker duality
- On balanced graphs
- Embedded associated primes of powers of square-free monomial ideals
- Clean tangled clutters, simplices, and projective geometries
- A SAT approach to branchwidth
- Single commodity-flow algorithms for lifts of graphic and cographic matroids
- The degree and regularity of vanishing ideals of algebraic toric sets over finite fields
- On circulant thin Lehman matrices
- Linear balanceable and subcubic balanceable graphs
- The positive circuits of oriented matroids with the packing property or idealness
- The computational complexity of the edge-perfect graph and the totally balanced packing game recognition problems
- Combinatorics of Cremona monomial maps
- On the vanishing ideal of an algebraic toric set and its parametrized linear codes
- Total dual integrality of triangle covering
- A survey on flows in graphs and matroids
- Delta minors, delta free clutters, and entanglement
- Packing, Covering and Partitioning Problems with Strongly Unimodular Constraint Matrices
- The hybrid electric vehicle-traveling salesman problem
- Broadcast domination in graphs
- scientific article; zbMATH DE number 3976364 (Why is no real title available?)
- Packing cycles exactly in polynomial time
- scientific article; zbMATH DE number 475604 (Why is no real title available?)
- Fractional packing in ideal clutters
- Packing arborescences in random digraphs
- The multilinear polytope for acyclic hypergraphs
- scientific article; zbMATH DE number 2159270 (Why is no real title available?)
- On circulant thin Lehman matrices
- Algebraic and combinatorial properties of ideals and algebras of uniform clutters of TDI systems
- Implosive graphs: square-free monomials on symbolic Rees algebras
- Resistant sets in the unit hypercube
- Tight cycle relaxations for the cut polytope
- Idealness of k-wise intersecting families
- On dyadic fractional packings of T-joins
- A tight relation between series-parallel graphs and bipartite distance hereditary graphs
- Disjoint dijoins for classes of dicuts in finite and infinite digraphs
- Clean clutters and dyadic fractional packings
- Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
- Broadcast domination and multipacking: bounds and the integrality gap
- Opposite elements in clutters
- Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
- Asymptotic resurgence via integral closures
- About the structure of the blocker of the hyperplanes of a matroid
- Polynomial algorithms for partitioning a tree into single‐center subtrees to minimize flat service costs
- scientific article; zbMATH DE number 2196275 (Why is no real title available?)
- scientific article; zbMATH DE number 2230198 (Why is no real title available?)
- Initial ideals of unimodular integer programs
- Combinatorial problems of packing and covering and related problems of integer linear program\-ming
- On Packing Dijoins in Digraphs and Weighted Digraphs
- Relation between broadcast domination and multipacking numbers on chordal graphs
This page was built for publication: Combinatorial optimization. Packing and covering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2716048)
