Extended formulations of lower-truncated transversal polymatroids. (4th May 2021)

• Record Type: Journal Article
• Authors: Imai, Hiroshi; Imai, Keiko; Hiraishi, Hidefumi
• Is Part Of: Optimization methods and software. Volume 36:Number 2/3(2021)
• Page Start: 326
• Page End: 331
• Publication Date: 2021-05-04
• Subjects: Matroid -- extension complexity -- network flow -- lower truncation; 05C21 -- 05B35; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1769619
• Languages: English
• ISSNs: 1055-6788

Abstract

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.