Abstract

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.