Education is not the filling of a pail, it is the lighting of a fire. - W. B. Yeats

 

NEWS in the Department of Mathematics
Funding/Grants REP/Awards/Announcements/Outreach

Karleigh Cameron
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.