Extended formulations of lower-truncated transversal polymatroids

DOI10.1080/10556788.2020.1769619zbMath1467.05028OpenAlexW3038398098MaRDI QIDQ4999331

Keiko Imai, Hidefumi Hiraishi, Hiroshi Imai

Publication date: 6 July 2021

Published in: Optimization Methods and Software (Search for Journal in Brave)

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

zbMATH Keywords

matroidnetwork flowextension complexitylower truncation

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Extended formulations for sparsity matroids
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• Using separation algorithms to generate mixed integer model reformulations
• Combinatorial bounds on nonnegative rank and extended formulations
• On combinatorial structures of line drawings of polyhedra
• Some \(0/1\) polytopes need exponential size extended formulations
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• Natural realizations of sparsity matroids
• Rado's theorem for polymatroids
• The Matching Polytope has Exponential Extension Complexity

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