Linear Programming

Authored by: Martin Dyer , Nimrod Megiddo , Emo Welzl

Discrete and Computational Geometry

Print publication date:  April  2004
Online publication date:  April  2004

Print ISBN: 9781584883012
eBook ISBN: 9781420035315
Adobe ISBN:


 Download Chapter



Linear programming has many important practical applications, and has also given rise to a wide body of theory. See Section 45.9 for recommended sources. Here we consider the linear programming problem in the form of maximizing a linear function of d variables subject to n linear inequalities. We focus on the relationship of the problem to computational geometry, i.e., we consider the problem in small dimension. More precisely, we concentrate on the case where d ? n, i.e., d = d(n) is a function that grows very slowly with n. By linear programming duality, this also includes the case n ? d. This has been called fixed-dimensional linear programming, though our viewpoint here will not treat d as constant. In this case there are strongly polynomial algorithms, provided the rate of growth of d with n is small enough.

Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.