[home] - [up] |
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
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.