Convex hierarchies, scheduling and symmetries

Abstract:

The Sum of Squares (SoS) hierarchy provides a finite nested family K_1, K_2, … , K_n of convex relaxations for an integer program with n variables, that reaches the integer hull, i.e., K_n corresponds to the convex hull of the integer feasible solution. A natural question is to understand how the integrality gap evolves over the family. In particular, a rapid decay of the gap might yield good approximation algorithms. We show that for the classic problem of scheduling identical machines to minimize the makespan, the SoS hierarchy exhibits an integrality gap curve that remains at least 1+ delta, for some small delta > 0, for K_j when j is linear on the number of jobs. In contrast, this problem admits polynomial time approximation schemes. In this talk I will (a) highlight the main ideas behind the construction of the lower bounds, and time permitting (b) explain why symmetries are in this case the main issue.

Posted on Sep 2, 2019 in ACGO, Seminars