NEWS in the Department of Mathematics
Date: Friday, August 26, 2016
Place: Weber 201
Time: 9:00 a.m.
Title: Bounding Curvature of the Central Curve in Linear Programming
Advisor: Dr. Dan Bates
Committee: Dr. Edwin Chong, Dr. Bailey Fosdick
Abstract: In linear programming, a multivariate linear function is optimized over a polytope of feasible points. Some algorithms find a solution by numerically tracking the central path from the analytic center of the polytope to the solution on the edge of the feasible region. The curvature of this curve has implications for the run-time of an algorithm. A more complete picture can be found by considering the curvature of the central curve, an extension of the central path. This paper discusses the results of De Loera, Sturmfels, and Vinzant in finding bounds for the curvature of the central curve by exploiting the geometry of the feasible region. Their methods use principles from matroid theory, algebraic combinatorics, and algebraic geometry.