Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2

DOI10.1016/J.DISC.2003.06.005MaRDI QIDQ1827668zbMATH OpenOpenAlexFDO

Authors Satoru Fujishige, Kazuhisa Makino, Takashi Takabatake, Kenji Kashiwabara

Publication date 6 August 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2003.06.005

zbMATH Keywords

base polyhedronpolybasic polyhedronsubmodular function

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Programming involving graphs or networks (90C35)

Review text

The concept of base polyhedra associated with submodular functions in combinatorial optimization [see the first author's book Submodular functions and optimization (Amsterdam etc.: North-Holland) (1991; Zbl 0728.90056)] is extended to polybasic polyhedra and some characterzations of such polyhedra are given. A polybasic polyhedron is a pointed convex polyhedron in \(\mathbb R^V\) whose edge vectors have support size at most 2, where \(V\) is a finite set. This new class of polyhedra includes base polyhedra, submodular polyhedra, generalized polymatroids, etc.

Recommendations

• Generalized polymatroids and submodular flows
• scientific article; zbMATH DE number 1379520
• scientific article; zbMATH DE number 1342137
• scientific article; zbMATH DE number 1303026
• A CHARACTERIZATION OF FACES OF THE BASE POLYHEDRON ASSOCIATED WITH A SUBMODULAR SYSTEM

Cites work

• A greedy algorithm for solving a certain class of linear programmes
• Convexity and Steinitz's exchange property
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Extension of M-convexity and L-convexity to polyhedral convex functions
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3906513 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• On structures of bisubmodular polyhedra
• Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability
• Pseudomatroids
• Submodular functions and optimization

Cited in

(9)

• Gross substitution, discrete convexity, and submodularity
• Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability
• Base polyhedra and the linking property
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• A CHARACTERIZATION OF FACES OF THE BASE POLYHEDRON ASSOCIATED WITH A SUBMODULAR SYSTEM
• Edge connectivity of the vertices of polyhedra
• The Orthant Non-Interaction Theorem for Certain Combinatorial Polyhedra and its Implications in the Intersection and the Dilworth Truncation of Bisubmodular Functions
• Subdivisions of integral base polytopes
• Zonotopes and the LP-Newton method

This page was built for publication: Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2

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