|
|
|
Session TC11 - Calcul polyhedral III / Polyhedral Computation III
Day |
Tuesday, May 10, 2005 |
Location |
Van Houtte |
Chair |
Antoine Deza |
Presentations
03h30 PM |
Radii Minimal Projections of Polytopes Andconstrained Optimization of Symmetric Polynomials |
|
Thorsten Theobald, TU Berlin and Yale University
We propose a new characterization of the radii minimal projections of polytopes onto $j$-dimensional subspaces in Euclidean space $mathbb{E}^n$. Applied on simplices this characterization allows to reduce the computation of an outer radius to a computation in the circumscribing case or to the computation of an outer radius of a lower-dimensional simplex. We use this characterization to determine the sequence of outer $(n-1)$-radii of regular simplices (which are the radii of smallest enclosing cylinders). This settles a question which arose from the incidence that a paper by Wei{ss}bach (1983) on this determination was erroneous.
(Joint work with Rene Brandenberg.)
|
03h55 PM |
PLCP-Orientations in Dimension Five and the Even Out-Degree Conjecture |
|
Sonoko Moriyama, University of Tokyo
Yoshio Okamoto, ETH-Zurich
The behavior of a certain pivoting algorithm for the linear complementarity problem with a P-matrix is represented by an orientation of a hypercube. In 1978, Stickney and Watson conjectured that such an orientation has no facet on which all even out-degree vertices appear. We prove it in dimension five.
|
04h20 PM |
Generating All Non-isomorphic Vertices for the Subtour Elimination Polytope |
|
Sylvia Boyd, University of Ottawa, S.I.T.E., 800 King Edward Ave., Ottawa, Ontario, Canada, K1N 6N5
Shichun Xiong, University of Ottawa, S.I.T.E., Ottawa, Ontario, Canada, K1N 6N5
We describe a method for finding all the non-isomorphic vertices for the subtour elimination polytope, which is a relaxation of the travelling salesman polytope. Due to the fact that the linear system associated with this polytope has a high degree of symmetry and degeneracy, many general vertex enumeration methods can be impractically slow on even small versions of this problem. The method we describe attempts to overcome such problems by exploiting known combinatorial properties of the structure of the vertices of this polytope. We give preliminary results which show that this method outperforms some general vertex enumeration software packages when applied to this problem, and discuss possible future directions for this research.
|
04h45 PM |
Comparing the strength of non-realizability certificates for oriented matroids |
|
Hiroki Nakayama, University of Tokyo, Information Science
To decide the non-realizability of an oriented matroid, tools such as
biquadratic final polynomials, non-Euclidean, and non-HK* are used as
a sufficient condition for non-realizability.
We focus on the class of rank-4 oriented matroids on an 8-element ground
set and compare the strength of those certificates. In particular, we show
biquadratic final polynomials are properly stronger than non-Euclidean.
(Joint work with Sonoko Moriyama, Komei Fukuda and Yoshio Okamoto.)
|
|