LEAST MAJORIZED ELEMENTS AND GENERALIZED POLYMATROIDS

• 成果类型: Article
• 署名作者: TAMIR, A
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.20.3.583
• 发表日期: 1995
• 页码: 583-589
• 关键词: flows; constraints; algorithm

摘要

We prove that a bounded generalized polymatroid has a least weakly submajorized (supermajorized) vector. Such a vector simultaneously minimizes every nondecreasing (nonincreasing), symmetric and quasi-convex function defined on the generalized polymatroid. The same result herds also for the set of integer vectors of a bounded integral generalized polymatroid. We then extend these results to more general sets, and discuss several computational aspects.