Thursday, March 25 2021
2:00pm - 2:45pm
Operations Research Seminar
The Role of Partition Polytopes in Data Analysis

The field of optimization, and polyhedral theory in particular, provides a powerful point of view on common tasks in data analysis. In this talk, we highlight the role of the so-called partition polytopes and their studies in clustering and classification.

The geometric properties of partition polytopes, such as their skeleton or their set of circuits, encode useful information on the underlying data set, and clusterings thereof. While a challenge in working with these polytopes lies in the lack of an explicit H-representation, they are linear projections of classical transportation polytopes, which allows a transfer of the geometric properties to algorithmic use. We cover some examples such as balanced least-squares assignments, classifiers in the form of generalized Voronoi diagrams, a measure for the robustness of a clustering, and the separation-preserving transformation of clusterings.
Speaker:Steffen Borgwardt
Affiliation:University of Colorado Denver

Download as iCalendar