Details:
Title  The central curve in linear programming.  Author(s)  Jesús A., Bernd Sturmfels, Cynthia Vinzant  Type  Article in Journal  Abstract  The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal of the central curve, thereby answering a question of Bayer and Lagarias. These invariants, along with the degree of the Gauss image of the curve, are expressed in terms of the matroid of the input matrix. Extending work of Dedieu, Malajovich and Shub, this yields an instancespecific bound on the total curvature of the central path, a quantity relevant for interiorpoint methods. The global geometry of central curves is studied in detail.  Keywords  Matroid, Tutte polynomial, Hyperbolic polynomial, Gauss map, Degree Curvature ,Total curvature, Projective variety, Gröbner basis ,Prime ideal  ISSN  16153375; 16153383/e 
URL 
http://link.springer.com/article/10.1007%2Fs1020801291277 
Language  English  Journal  Found. Comput. Math.  Volume  12  Number  4  Pages  509540  Publisher  Springer US, New York, NY  Year  2012  Edition  0  Translation 
No  Refereed 
No 
