David Avis - McGill University and GERAD

Hypermetric Relaxations of Max-Cut

Abstract: We consider tight linear programming relaxations for the max cut problem in graphs, based on k-gonal (hypermetric) inequalities. We show that the integrality ratio for random dense graphs is asymptotically 1+1/k and for random sparse graphs is at least 1+3/k. There are O(n ^ k ) k-gonal inequalities. These results generalize work by Poljak and Tuza, who gave similar results for k=3. The talk will also discuss properties of two related polyhedra, the cut polytope and the metric polytope.

Joint work with Jun Umemoto.

Colloquium - 16:00

Carsten Lange - Technische Universität Berlin

On diameters of some simple polytopes - a curvature approach

Abstract: A path between a pair of vertices is a sequence of edges such that consecutive edges share a vertex. The length of a path is the number of its edges.

What is the the maximal length of a shortest path between any two points of a simple polytope?

The method I shall present to obtain an upper bound uses two ingredients: varying a hypothetical shortest path and assuming the polytope to be positively curved in the original sense of Forman, who also introduced this method.

In the end, I shall indicate a direction how a more general definition of curvature can be used.