| [home] - [up] |
Abstract: Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In this talk I try to overview the interrelation of these topics. We study problems where both parity and connectivity requirements are imposed. For example, a characterization is given for undirected graphs having a k-edge-connected orientation for which the in-degree of every node v is congruent to q(v) (mod 2) for every "compatible" parity prescriptions q:V\rightarrow {0,1}.
Colloquium - 16:00
Abstract: The power of linear programming, one of today's most important optimization techniques, is - to a large extent - based on deep insights into the interplay between the geometry and algebraic description of polyhedra.
A new method of description is implied by recent results in real-algebraic geometry: Polyhedra fall into the class of basic closed semi-algebraic sets, the intersections of solutions of finitely-many non-strict polynomial inequalities. Due to a deep result of Bröcker and Scheiderer, every n-dimensional basic closed semi-algebraic set (and hence every n-dimensional polyhedron) can be described by at most n(n+1)/2 polynomial inequalities. Surprisingly, this is true independently on the combinatorial, algebraic, or geometric complexity of the set. Unfortunately all known proofs of this general result are non-constructive.
In this talk we present two new results on the description of polyhedra by polynomial inequalities: The number of polynomials needed is reduced from quadratic to linear (2n-1 inequalities suffice) and an explicit construction of such systems of polynomials is given. The general case will be deduced from a visual tour through the constructions in dimensions n=2 and n=3, the possibilites of different approaches will be discussed.