Extended Formulations for Sparsity Matroids

2014/03/28 by Satoru Iwata, Naoyuki Kamiyama, Iwata, Satoru +7
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #math.CO #math.OC

paper · pdf · doi:10.48550/arxiv.1403.7272

10 pages

arxiv created 2014/03/28 · arxiv updated 2014/03/31

Abstract

We show the existence of a polynomial-size extended formulation for the base polytope of a (k,ℓ)-sparsity matroid. For an undirected graph G=(V,E), the size of the formulation is O(|V||E|) when k ≥ ℓ and O(|V|² |E|) when k ≤ ℓ. To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.

Related

• Natural realizations of sparsity matroids
• Extended formulations for matroid polytopes through randomized protocols
• Constant-Time Algorithms for Sparsity Matroids
• Robust Sparsification for Matroid Intersection with Applications
• A Method to construct the Sparse-paving Matroids over a Finite Set