Extended formulations for sparsity matroids

被引：6

作者：

Iwata, Satoru ^{[1
]}

Kamiyama, Naoyuki ^{[2
]}

Katoh, Naoki ^{[3
]}

Kijima, Shuji ^{[4
]}

Okamoto, Yoshio ^{[5
]}

机构：

[1] Univ Tokyo, Dept Math Informat, Tokyo, Japan

[2] Kyushu Univ, Inst Math Ind, Fukuoka 812, Japan

[3] Kyoto Univ, Dept Architecture & Architectural Engn, Kyoto, Japan

[4] Kyushu Univ, Dept Informat, Fukuoka 812, Japan

[5] Univ Electrocommun, Grad Sch Informat & Engn, Dept Commun Engn & Informat, Chofu, Tokyo 182, Japan

来源：

MATHEMATICAL PROGRAMMING | 2016年 / 158卷 / 1-2期

基金：

日本学术振兴会;

关键词：

GRAPHS; ALGORITHMS; RIGIDITY; MODEL;

D O I：

10.1007/s10107-015-0936-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：565 / 574

页数：10

共 16 条

[1]

Conforti M., 2015, ARXIV150202817CSDM

[2]

Edmonds J., 1971, MATH PROGRAM, V1, P127, DOI DOI 10.1007/BF01584082

[3] Extended formulations, nonnegative factorizations, and randomized communication protocols [J].