Accueil
Affiche (PDF)
 
Participants
Programme
Inscription
Site
Hébergement
Liens
 
 
Éditions précédentes
2004
2003
2002


    

Séance TC11 - Calcul polyhedral III / Polyhedral Computation III

Jour mardi, le 10 mai 2005
Salle Van Houtte
Président Antoine Deza

Présentations

15h30 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.)


15h55 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.


16h20 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.


16h45 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.)