On cardinality constrained polymatroids

This paper extends results on the cardinality constrained matroid polytope presented in [Maurras, J. F. and R. Stephan, On the cardinality constrained matroid polytope, arXiv:0902.1932 (2009). To appear in Networks] to polymatroids. Given a polymatroid Pf(S) defined by an integer submodular function f on some set S and an increasing finite sequence c of natural numbers, the cardinality constrained polymatroid is the convex hull of the integer points x ∈ Pf(S) whose sum of all entries is a member of c. We give a complete linear description for this polytope. Moreover, we characterize some facets of the cardinality constrained version of Pf(S) and briefly investigate the separation problem for this polytope. We close with a conjecture about a complete linear description of the intersection of two cardinality constrained polymatroids defined on the same ground set. © 2010 Elsevier B.V