Extended formulations for sparsity matroids

• 成果类型: Article
• 署名作者: Iwata, Satoru; Kamiyama, Naoyuki; Katoh, Naoki; Kijima, Shuji; Okamoto, Yoshio
• 署名单位: University of Tokyo; Kyushu University; Kyoto University; Kyushu University; University of Electro-Communications - Japan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0936-8
• 发表日期: 2016
• 页码: 565-574
• 关键词: graphs; algorithms; RIGIDITY; MODEL

摘要

We show the existence of a polynomial-size extended formulation for the base polytope of a -sparsity matroid. For an undirected graph , the size of the formulation is when and when . To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.