When: January 28, 2015, 12:30 PM
Contact: 608-316-4401, firstname.lastname@example.org
Polyhedral Results on the Stable Set Problem and on Half-Integral Polytopes
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.
SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.
Speaker: Carla Michini