Los puntos clave no están disponibles para este artículo en este momento.
O (n) time algorithms for linear programming problems with two or three variables and n constraints are described. The approach uses convexity, dominance of linear functions and linear-time median finding algorithms. The algorithms improve the previously known best bounds of O (n n) time for both of these problems.
Martin Dyer (Wed,) studied this question.