Setpair Formulations and Some Applications
Adrian Vetta, School of Compputer Science, McGill University

Abstract : We investigate the class of integer programs for which the constraint system is based upon pairs of sets in an underlying graph. One source of interest in such formulations is that they encapsulate a range of fundamental graph problems. The properties of these integer programs are examined (in particular, the structure of basic solutions to the linear programming relaxations of these formulations) and then used in the design of good algorithms for the aforementioned problems.

Announcement Poster in PDF