Extended formulations for sparsity matroids
Extended formulations for sparsity matroids
复制标题
稀疏拟阵的扩展公式
DOI：
10.1007/s10107-015-0936-8
复制
发表时间：
2016
影响因子：
2.7
通讯作者：
and Yoshio Okamoto
中科院分区：
文献类型：
--
作者：
Satoru Iwata;Naoyuki Kamiyama;Naoki Katoh;Shuji Kijima;and Yoshio Okamoto
我们证明了a-稀疏拟阵的基多面体的多项式大小的扩展公式的存在性。对于无向图，公式的大小为when和when。为此，我们采用Faenza等人最近开发的技术，该技术使用随机通信协议。
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 iswhenandwhen. To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.