Extended formulations for matroid polytopes through randomized protocols

DOI10.1016/J.ORL.2022.01.011MaRDI QIDQ2670489zbMATH OpenOpenAlexFDO

Authors Manuel Aprile

Publication date 11 March 2022

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.12453

zbMATH Keywords

extended formulationsmatroid polytopematroidsradial conesrandomized protocolspanning tree polytope

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• Extended formulations for sparsity matroids
• Extended formulations for independence polytopes of regular matroids
• Regular matroids have polynomial extension complexity

Cites work

• 2L_enum
• A Very General Theorem on Systems of Distinct Representatives
• Adjacency on polymatroids
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Communication Complexity
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Extended formulations for sparsity matroids
• Extended formulations in combinatorial optimization
• Extension complexity of stable set polytopes of bipartite graphs
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• Matroid polytopes, nested sets and Bergman fans
• Matroids and the greedy algorithm
• On linear systems with integral valued solutions
• On the combinatorial lower bound for the extension complexity of the spanning tree polytope
• Recent advances on the log-rank conjecture in communication complexity
• Recognizing Cartesian products of matrices and polytopes
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
• Some \(0/1\) polytopes need exponential size extended formulations
• Subgraph polytopes and independence polytopes of count matroids
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(10)

• Polymatroids: Construction and random algorithms
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Towards a polynomial-time randomized algorithm for closed product-form networks
• A tight approximation algorithm for the cluster vertex deletion problem
• The role of rationality in integer-programming relaxations
• Extended formulations for matroid polytopes through randomized protocols
• Slack matrices, k-products, and 2-level polytopes
• Face enumeration for split matroid polytopes
• Exact approaches for the connected vertex cover problem
• The total matching polytope of complete bipartite graphs

Describes a project that uses

Uses Software

• 2L_enum

This page was built for publication: Extended formulations for matroid polytopes through randomized protocols

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