Extended formulations of lower-truncated transversal polymatroids. (4th May 2021) - Imai, Hiroshi; Imai, Keiko; Hiraishi, Hidefumi
Abstract : Extended formulations of ( k, l ) -sparsity matroids defined on graphs with n vertices and m edges are investigated by Iwata et al. [ Extended formulations for sparsity matroids, Math. Program. 158 (2016), pp. 565–574]. This note interprets results on ( k, l ) -lower-truncated transversal polymatroids by the first author in 1983, from the viewpoint of extended formulations, and shows the same O ( m n ) bound when k ≥ l and a better bound O ( m 2 ) when k < l . A unified polymatroidal approach is given to derive more general understanding.