Session WA10 - Calcul polyédrique II / Polyhedral Computation II
Day Wednesday, May 06, 2009 Room Dutailier International President David Avis
Presentations
|
10h30 AM- 10h55 AM |
Experimental Combinatorics for Convex Polytopes |
|
William Hua, McMaster University, Computing and Software, 1280 Main Street West, Hamilton, Ontario, Canada, L8S 4K1 The Hirsch conjecture is a 50 year old conjecture related to the worst case performance of the simplex method of linear programming. In this talk, I will discuss the recent work of David Bremner and Lars Schewe on a computational attack on this conjecture, and further computational experiments. |
|
10h55 AM- 11h20 AM |
Fat Shattering Dimension and Maximum Width Simplices |
|
David Bremner, University of New Brunswick, Faculty of Computer Science, Canada René Brandenburg, TU München, Germany The related notions of margin (between parallel separating hyperplanes) and "fat shattering dimension" provide error bounds for pattern classifiers. This talk considers the generalization of this framework to more general Minkowski (i.e. convex) norms. A central notion is the maximum (Minkowski norm) width of a j-simplex in a convex container(with "width" suitably generalized for subdimensional sets). |
|
11h20 AM- 11h45 AM |
Proximity and Bichromatic Matching on Planar Crystal Lattices |
|
Norie Fu, University of Tokyo, Computer Science, 7-3-1 Hongo, Bunkyo-ku, Tokyo, Japan, 113-8656 Hiroshi H.I. Imai, University of Tokyo, Computer Science, 7-3-1 Hongo, Bunkyo-ku, Tokyo, Japan, 113-8656 Surfaces of crystals have lattice structures of atoms including one of the most typical one, the honeycomb lattice. Motivated by optimizing the atom sliding operation at the surfaces, Voronoi diagrams and bichromatic matching are investigated on the honeycomb lattice. Geometry really helps in various problems on such discrete lattices. |
|
11h45 AM- 12h10 PM |
The Directed Cut Polytope and Applications to Mining Optimization |
|
David Avis, GERAD, McGill University, Computer Science, 3480 University St., Montréal, Québec, Canada, H3A 2A7 Conor Meagher, McGill University, Computer Science, 3480 University Street, McConnell Engineering Building, Room 318, Montreal, Quebec, Canada, H3A 2A7 We present structural properties of the directed cut polytope. In particular, we show that this polytope is the convex hull of two cut polytopes and its dimension is binom(n,2)+n-1. New facets of the directed cut polytope are presented based on bijections from known facets of the cut polytope. |