|Duration:||July 2003 - August 2004|
|Project director:||Prof. Dr. M. Grötschel|
Institut für Mathematik der TU Berlin
Straße des 17. Juni 136, Office: MA 302
10623 Berlin, Germany
|Tel: +49 30 84185-210 (office) / +49 30 84185-209 (secretary)|
|Responsible||Assistant Professor Dr. Hartwig Bosse (Former PhD student and collaborator at TU Berlin)|
|email (now): firstname.lastname@example.org|
|Support||DFG Research Center Matheon "Mathematics for Key Technologies"|
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. As all known proofs of the Bröcker-Scheiderer result are non-constructive, an explicit construction of such systems of polynomials has been only recently discovered within this research group (,).
The aim of this project is to further explore the new proof technique and implement the algorithm that is the basis of this result. New strategies for the solution of combinatorial optimization problems will be examined by adapting the results to special classes of combinatorially interesting polyhedra. Finally, general principles used in the theory of polyhedra, such as homogenization, are to be investigated with respect to their applicability in algebraic geometry.
|||C. Scheiderer: Stability index of real varieties. Inventiones Math. 97 (1989), no.3, 467-483.|
|||L. Bröcker: On basic semialgebraic sets. Expo. Math. 9 (1991), 289-334.|
|||J. Bochnak, M. Coste, and M.-F. Roy: Real algebraic geometry. Springer, New York, 1998.|
|||H. Bosse, M. Grötschel, and M. Henk: Polynomial inequalities representing polyhedra. Submitted for publication.|
|||H. Bosse: Describing polyhedra by polynomial inequalities. Master's thesis, Technische Universität Berlin, 2003.|