Characterizing and recognizing generalized polymatroids

András Frank, Tamás Király, Júlia Pap, David Pritchard

Published in:
Mathematical Programming, DOI:10.1007/s10107-013-0685-5


Generalized polymatroids are a family of polyhedra with several nice properties and applications. One property of generalized polymatroids used widely in existing literature is "total dual laminarity;" we make this notion explicit and show that only generalized polymatroids have this property. Using this we give a polynomial-time algorithm to check whether a given linear program defines a generalized polymatroid, and whether it is integral if so. Additionally, whereas it is known that the intersection of two integral generalized polymatroids is integral, we show that no larger class of polyhedra satisfies this property.

Previous version can be found here.

Bibtex entry:

AUTHOR = {Frank, Andr{\'a}s and Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia and Pritchard, David},
TITLE = {Characterizing and recognizing generalized polymatroids},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-03}

Last modification: 13.3.2018. Please email your comments to Tamás Király!