Text

Regular Matroids Have Polynomial Extension Complexity

We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n2) 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(n2) bound.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.1 February 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 540-559

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

EXTENDED FORMULATIONS
REGULAR MATROIDS
INDEPENDENCE POLYTOPE
SPANNING TREE POLYTOPE
CUT DOMINANT

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1137

Pernyataan Tanggungjawab

Manuel Aprile, Samuel Fiorini

Versi lain/terkait

Lampiran Berkas

Komentar