TR-2012-03

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.

• April_2012

Bibtex entry:

@techreport{egres-12-03,

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-03}

}