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


    

Séance MB11 - Calcul polyhedral I / Polyhedral Computation I

Jour lundi, le 09 mai 2005
Salle Van Houtte
Président David Avis

Présentations

15h30 Primal--Dual Algorithms for Data Depth
  Vera Rosta, Hungarian Academy of Sciences, Rényi Institute of Mathematics

The halfspace depth of a point $p$ relative to a data set $S$ in $d$-dimension is the smallest number of data observations from $S$ in any closed halfspace containing $p$. A point with largest depth was considered as the generalization of the median of $S$ by Tukey. The computation of the halfspace depth of a point is equivalent to the closed hemisphere problem, which was shown to be NP-complete by Johnson and Preparata. We propose primal--dual algorithms that update both an upper bound and a lower bound of the depth and terminate as soon as the two bounds coincide. We report preliminary computational experiments. (Joint work with D. Bremner and K. Fukuda)


15h55 Separation Made Easier
  David Bremner, University of New Brunswick

Whether two sets are seperable by hyperplanes is invariant under affine transformations, while distance is not. The near universal reduction of separation problems in practice to distance computations is on the surface thus a bit of a mystery. In this talk I will argue that the connection between distance and separation is necessary and natural as soon as one asks for the ``best'' separating hyperplane. On the other hand, it is often much more convenient to work with distance metrics different from the standard Euclidean one. It turns out that for polytopal metrics a strong duality relationship between distance and separation allows the straightforward computation of optimal separating hyperplanes by solving a primal-dual pair of linear programs. An interesting feature of this framework is that it works for input given explicitly as sets of points (where an LP solution is relatively well known, even for the Euclidean metric), but also for input given implicitly as intersections of halfspaces and Minkowski sums of line segments. I will round out the talk by discussing some possible approaches to the case when two sets are not separable by a hyperplane, and some motivation from problems in pattern classification. (Joint work with Thomas Burger and Peter Gritzmann)


16h20 Geometry of Cycling in the Simplex Method
  David Titley-Péloquin, McGill University, Computer Science
David Avis, McGill University, Computer Science, 3480 University St., Montréal, Québec, Canada, H3A 2A7
Bohdan Kaluzny, McGill University, Computer Science

In this talk I present the dual geometry of cycling in the simplex method. A geometric interpretation of the dual can be used not only to visualize cycles - such as Hoffman's famous ``circle'' - but also to construct cyclic linear programs. In fact, I show how to build a linear program, bounded or unbounded, containing a cycle of arbitrary length. This leads to the derivation of a lower bound of $\Omega(n)$ for the maximal cycle length of a linear program in m variables and n inequality constraints.