Extended formulations of lower-truncated transversal polymatroids
Extended formulations of lower-truncated transversal polymatroids
复制标题
下截断横向多拟阵的扩展公式
DOI：
10.1080/10556788.2020.1769619
复制
发表时间：
2020
影响因子：
2.2
通讯作者：
Hiraishi Hidefumi
中科院分区：
文献类型：
--
作者：
Imai Hiroshi;Imai Keiko;Hiraishi Hidefumi
Iwata等人研究了在有顶点和边的图上定义的稀疏拟阵的扩展公式。程序，158 (2016),pp. 565-574]。本文从推广公式的角度解释了第一作者1983年关于下截截横切多阵的结果，并给出了当<l时的相同界和一个更好的界。给出了一个统一的多母线方法，以获得更普遍的理解。
Extended formulations of-sparsity matroids defined on graphs withnvertices andmedges are investigated by Iwata et al. [Extended formulations for sparsity matroids, Math. Program. 158 (2016), pp. 565–574]. This note interprets results on-lower-truncated transversal polymatroids by the first author in 1983, from the viewpoint of extended formulations, and shows the samebound whenand a better boundwhenk<l. A unified polymatroidal approach is given to derive more general understanding.