Regular Matroids Have Polynomial Extension Complexity

• 成果类型: Article
• 署名作者: Aprile, Manuel; Fiorini, Samuel
• 署名单位: University of Padua; Universite Libre de Bruxelles
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1137
• 发表日期: 2022
• 页码: 540-559
• 关键词: independence polytopes; MODEL

摘要

We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n(6)). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n(2)) bound for the special case of (co)graphic matroids. However, the case of a general regular matroid was open, despite recent attempts. We also consider the extension complexity of circuit dominants of regular matroids, for which we give a O(n(2)) bound.