Speaker: Walter Morris, George Mason University
Date and time: Thursday, September 20, 4-5pm
Place: Phillips 110
Title: A proof of the strict monotone 5-step conjecture
Abstract: The strict monotone d-step conjecture for linear programming says that, given a d-dimensional polytope P with 2d facets and a linear function f, there is a path in the graph of P from the vertex with minimum f value to the vertex with maximum f value that is increasing in f and contains at most d edges. Santos (2012) showed that this conjecture is false for d sufficiently large, but the largest d for which it is true is not known. For d=5 we created a logical statement that is unsatisfiable if there is no counterexample. The satisfiablility solver that we used showed that there is no counterexample.
Thu, September 20, 2018
4:00 p.m. - 5:00 p.m.