Characterizing and recognizing generalized polymatroids

• 成果类型: Article
• 署名作者: Frank, Andras; Kiraly, Tamas; Pap, Julia; Pritchard, David
• 署名单位: Eotvos Lorand University; Princeton University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0685-5
• 发表日期: 2014
• 页码: 245-273
• 关键词: integrality; systems

摘要

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.