Characterizing and recognizing generalized polymatroids
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Nonnumerical algorithms (68W05) Linear programming (90C05) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
A generalized polymatroid is a polyhedron given by supermodular and submodular functions p and b, both mapping the empty set to zero and satisfying a ``cross-inequality. Generalized polymatroids generalize polymatroid, contra-polymatroids, base-polyhedra, and submodular polyhedra. This paper focuses on characterizations and recognition complexity of generalized polymatroids. The main results are the following: A polyhedron is a generalized polymatroid if it can be defined by set functions p,b such that for every primal objective with finite value some optimal solution is ``laminar, where the latter is a combinatorial property of the support of the solution. While it is shown that verifying the above characterization is NP-hard, the authors give a polynomial-time algorithm that given a system of linear inequalities checks if a polyhedron is a generalized polymatroid. Another result is that the known property of integral generalized polymatroids that their intersection is integral in fact characterizes them in the following sense: If the intersection of a polyhedron P with every integral generalized polymatroid is integral, then P is a generalized polymatroid. Finally, bounded generalized polymatroids are characterized as satisfying certain Minkowski sum equations related to generalized permutahedra.
- A note on Frank's generalized polymatroids
- A Survey on Covering Supermodular Functions
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Convexity and Steinitz's exchange property
- Covering skew-supermodular functions by hypergraphs of minimum total size
- Discrete convexity and unimodularity. I.
- Faces of generalized permutohedra
- Generalized polymatroids and submodular flows
- scientific article; zbMATH DE number 3862931 (Why is no real title available?)
- scientific article; zbMATH DE number 3970767 (Why is no real title available?)
- scientific article; zbMATH DE number 3970769 (Why is no real title available?)
- scientific article; zbMATH DE number 3562067 (Why is no real title available?)
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- Is submodularity testable?
- Lifted generalized permutahedra and composition polynomials
- Matroid polytopes and their volumes
- Matroids and the greedy algorithm
- On recognizing integer polyhedra
- Permutohedra, Associahedra, and Beyond
- Proving total dual integrality with cross-free families—A general framework
- Recognizing conic TDI systems is hard
- The complexity of recognizing linear systems with certain integrality properties
- Base polyhedra and the linking property
- A Geometric Characterization of Poly-antimatroids
- scientific article; zbMATH DE number 3906513 (Why is no real title available?)
- scientific article; zbMATH DE number 4023308 (Why is no real title available?)
- A NOTE ON THE DECOMPOSITION OF POLY-LINKING SYSTEMS AND THE MINORS OF GENERALIZED POLYMATROIDS
- Recognizing Polymatroids Associated with Hypergraphs
- Least Majorized Elements and Generalized Polymatroids
- A characterization of network representable polymatroids
- Supermodular extension of Vizing's edge-coloring theorem
- On the support of Grothendieck polynomials
- Random allocations of multiple objects with incomplete information
- A note on Frank's generalized polymatroids
This page was built for publication: Characterizing and recognizing generalized polymatroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403645)
