Title: Solving Linear Programs without Breaking Abstractions
Speaker: Matt Anderson, Union College
Date: Wednesday, March 22, 2017 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We draw connections between descriptive complexity theory and combinatorial optimization to show that the ellipsoid method for solving linear programs can be implemented in a way that respects the abstractions and symmetry of the program being solved. That is to say, there is an algorithmic implementation of the method that does not distinguish, or make choices, between variables or constraints in the program unless they are distinguished by properties definable from the linear program.
In particular, we demonstrate that the solvability of linear programs can be expressed in fixed-point logic with counting (FPC) as long as the program is given by a separation oracle that is itself definable in FPC. We use this to show that the size of a maximum matching in a graph is definable in FPC. This refutes a conjecture first posed by Blass, Gurevich and Shelah (1999). On the way to defining a suitable separation oracle for the maximum matching program, we provide FPC formulas defining canonical maximum flows and minimum cuts in undirected weighted graphs. This is joint work with Anuj Dawar.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S17/