No label defined (Q4401028)

Linear programming has many important practical applications, and has also given rise to a wide body of theory. 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\ll 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\ll 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. The plan of the chapter is as follows. First we consider the simplex method, we review deterministic linear time algorithms and randomized algorithms, and we consider the derandomization of the latter. We examine parallel algorithms for this problem, and finally we briefly discuss related issues. The emphasis throughout is on complexity-theoretic bounds for the linear programming problem. For the entire collection see [Zbl 0890.52001].