Extended formulations for matroid polytopes through randomized protocols

DOI10.1016/j.orl.2022.01.011OpenAlexW4220775035MaRDI QIDQ2670489

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

matroidsextended formulationsmatroid polytopespanning tree polytoperandomized protocolradial cones

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (3)

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ The role of rationality in integer-programming relaxations ⋮ A tight approximation algorithm for the cluster vertex deletion problem

Uses Software

• 2L_enum

Cites Work

• Unnamed Item
• 2L_enum
• Extended formulations for sparsity matroids
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• On linear systems with integral valued solutions
• Matroid polytopes, nested sets and Bergman fans
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Using separation algorithms to generate mixed integer model reformulations
• Expressing combinatorial optimization problems by linear programs
• Extension complexity of stable set polytopes of bipartite graphs
• Enumeration of 2-level polytopes
• Subgraph polytopes and independence polytopes of count matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Recognizing Cartesian products of matrices and polytopes
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• On the combinatorial lower bound for the extension complexity of the spanning tree polytope
• Some \(0/1\) polytopes need exponential size extended formulations
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• Adjacency on polymatroids
• The Matching Polytope has Exponential Extension Complexity
• Communication Complexity
• Recent advances on the log-rank conjecture in communication complexity
• A Very General Theorem on Systems of Distinct Representatives
• Matroids and the greedy algorithm
• Extended formulations from communication protocols in output-efficient time
• Extended formulations in combinatorial optimization

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