@misc{Stephan, author = {Stephan, R{\"u}diger}, title = {On the cardinality constrained matroid polytope}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10614}, number = {08-08}, abstract = {Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Gr{\"o}tschel's cardinality forcing inequalities, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.}, language = {en} } @misc{Stephan, author = {Stephan, R{\"u}diger}, title = {Facets of the (s,t)-p-path polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9328}, number = {06-38}, abstract = {\noindent We give a partial description of the \$(s,t)-p\$-path polytope of a directed graph \$D\$ which is the convex hull of the incidence vectors of simple directed \$(s,t)\$-paths in \$D\$ of length \$p\$. First, we point out how the \$(s,t)-p\$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the \$p\$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length \$p\$ in \$D\$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for \$(s,t)\$-paths of cardinality at most \$p\$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the \$(s,t)-p\$-path polytope.}, language = {en} } @misc{KaibelStephan, author = {Kaibel, Volker and Stephan, R{\"u}diger}, title = {On cardinality constrained cycle and path polytopes}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10093}, number = {07-25}, abstract = {We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.}, language = {en} } @incollection{Groetschel2004, author = {Gr{\"o}tschel, Martin}, title = {Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes}, series = {The Sharpest Cut}, booktitle = {The Sharpest Cut}, editor = {Gr{\"o}tschel, Martin}, publisher = {MPS-SIAM}, pages = {99 -- 120}, year = {2004}, language = {en} } @article{KaibelStephan2010, author = {Kaibel, Volker and Stephan, R{\"u}diger}, title = {On cardinality constrained cycle and path polytopes}, series = {Math. Program.}, volume = {123}, journal = {Math. Program.}, number = {2 (A)}, doi = {10.1007/s10107-008-0257-2}, pages = {371 -- 394}, year = {2010}, language = {en} } @misc{MaurrasStephan2009, author = {Maurras, Jean and Stephan, R{\"u}diger}, title = {On the cardinality constrained matroid polytope}, year = {2009}, language = {en} } @book{Stephan2005, author = {Stephan, R{\"u}diger}, title = {Polytopes associated with length restricted directed circuits}, publisher = {diploma thesis, Technische Universit{\"a}t Berlin}, year = {2005}, language = {en} } @article{Stephan2009, author = {Stephan, R{\"u}diger}, title = {Facets of the (s,t)-p-path polytope}, series = {Discrete Appl. Math.}, volume = {157}, journal = {Discrete Appl. Math.}, number = {14}, doi = {10.1016/j.dam.2009.06.003}, pages = {3119 -- 3132}, year = {2009}, language = {en} }