Martin Henk - Technische Universität Wien

Representation of polyhedra by polynomials

Abstract: Results of Bröcker and Scheiderer on the stability index of basic semi-algebraic sets imply, as a very special case, that every d-dimensional polyhedron admits a representation as the set of solutions of at most d(d+1)/2 polynomial inequalities. The interior of a polyhedra can even be described by d polynomials. However, no construction of such a system of polynomials is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension.

Starting with the 2-dimensional case and some basic properties of polynomials describing polyhedra, we give, for simple polytopes, an explicit construction of such a system of polynomials. The number of used polynomials, however, is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number d(d+1)/2.

Finally, we discuss some generalizations and potential applications to combinatorial optimization problems.

This is part of a joint work with Martin Grötschel.

Colloquium - 16:00

Adrian Zymolka - Konrad-Zuse-Zentrum Berlin

On generalizations of set packing

Abstract: One of the most studied structures in combinatorial optimization is set packing. Two special cases are the matching problem and the stable set problem where in fact the latter is equivalent to set packing. For matching, an obvious generalization is (integer) b-matching. In this talk, we propose similar generalizations for set packing and stable set, which we call multi-set packing and stable multi-sets, respectively. We show that the generalized problems are not equivalent but that stable multi-set is a proper special case of multi-set packing.

Our investigation of the new structures focuses on polyhedral properties of stable multi-sets. For this problem, reduction rules are derived and the associated polytope is studied. We state necessary and sufficient conditions for the linear relaxation polytope to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, several classes of inequalities known for stable sets are generalized together with conditions for them to be facet defining.

This is joint work with Arie Koster.