000124915 001__ 124915
000124915 005__ 20181221101940.0
000124915 0247_ $$2doi$$a10.22028/D291-25909
000124915 037__ $$aTHESIS_LIB
000124915 245__ $$aGomory-chvatal cutting planes and the elementary closure of polyhedra
000124915 260__ $$bUniversität des Saarlandes$$c2000
000124915 269__ $$a2000
000124915 336__ $$aTheses
000124915 520__ $$aThe elementary closure P'; of a polyhedrom P is the intersection of P with all its Gomory-Chvátal cutting planes. P'; is a rational polyhedron provided that P is rational. The Chvátal-Gomory procedure is the iterative application of the elementary closure operation to P. The Chvátal rank is the minimal number of iterations needed to obtain P_I. It is always finite, but already in |R² one can construct polytopes of arbitrary large Chvátal rank. We show that the Chvátal rank of polytopes contained in the n-dimensional 0/1 cube is O(n² log n) and prove the lower bound (1+E) n, for some E> 0. We show that the separation problem for the elementary closure of a rational polyhedron is NP-hard. This solves a problem posed by Schrijver. Last we consider the elementary closure in fixed dimension. the known bounds for the number of inequalities defining P'; are exponential, even fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone from this polynomial description in fixed dimension with a maximal degree of violation in a natural sense.
000124915 700__ $$0240331$$g183121$$aEisenbrand, F.
000124915 720_2 $$aBockmayr, Alexander$$edir.
000124915 909C0 $$0252111$$pDISOPT$$xU11879
000124915 909CO $$pSB$$ooai:infoscience.tind.io:124915
000124915 917Z8 $$x148230
000124915 937__ $$aDISOPT-THESIS-2008-001
000124915 973__ $$sPUBLISHED$$aOTHER
000124915 980__ $$aTHESIS