The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Polyhedral results on the stable set problem and on half-integral polytopes

Carla Michini, Post-doc at WID

Date and Time: Jan 28, 2015 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


In many optimization problems the set of feasible solutions can be described or approximated through a polyhedron. In this talk, I will focus on the polyhedral structure of specific classes of polytopes.

First, I will introduce the fractional stable set polytope, that arises from the edge formulation of the stable set problem and is half-integral. I will present a graphic characterization of vertices and vertex adjacency for this polytope, and I will describe how to use this knowledge for algorithmic purposes, showing that the diameter of the polytope cannot exceed the number of nodes of the input graph.

Then, I will present some more general results concerning the diameter of lattice polytopes, i.e. polytopes whose vertices are integral. I will show a new bound on the diameter of these polytopes and an algorithm to find a path between two given vertices, whose length does not exceed the bound. These results imply that the diameter of a n-dimensional half-integral polytope is at most 3/2 n, and I will show that this bound is tight.