On cardinality constrained polymatroids
(2010) Electronic Notes in Discrete Mathematics — Vol. 36, n° C, p. 1017-1024 (2010)
Files
1-s2.pdf
Restricted Access - Adobe PDF
- 227.31 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Stephan, R., & Spiegelberg, I. (2010). On cardinality constrained polymatroids. Electronic Notes in Discrete Mathematics, 36(C), 1017-1024. https://doi.org/10.1016/j.endm.2010.05.129 (Original work published 2010)