Extended formulations of lower-truncated transversal polymatroids

DOI10.1080/10556788.2020.1769619MaRDI QIDQ4999331zbMATH OpenOpenAlexFDO

Authors Keiko Imai, Hidefumi Hiraishi, Hideki Imai

Publication date 6 July 2021

Published in Optimization Methods \& Software (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1080/10556788.2020.1769619

zbMATH Keywords

network flowmatroidextension complexitylower truncation

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Extended formulations for sparsity matroids
• Extended formulations for independence polytopes of regular matroids
• Extended formulations in combinatorial optimization
• Subgraph polytopes and independence polytopes of count matroids
• Uncapacitated flow-based extended formulations

Cites work

• scientific article; zbMATH DE number 1953186 (Why is no real title available?)
• Combinatorial bounds on nonnegative rank and extended formulations
• Connections in combinatorial optimization
• Extended formulations for sparsity matroids
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• Natural realizations of sparsity matroids
• On combinatorial structures of line drawings of polyhedra
• Rado's theorem for polymatroids
• Some \(0/1\) polytopes need exponential size extended formulations
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(4)

• Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
• Extended formulations for sparsity matroids
• Extended formulations for independence polytopes of regular matroids
• Truncation Technique for Characterizing Linear Polymatroids

This page was built for publication: Extended formulations of lower-truncated transversal polymatroids

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