MIT 公开课 - 高等算法 lec22.pdfVIP

MIT OpenCourseWare 6.854J / 18.415J Advanced Algorithms Fall 2008 �� For information about citing these materials or our Terms of Use, visit: /terms. 18.415/6.854 Advanced Algorithms December 1, 2008 Lecture 22 Lecturer: Michel X. Goemans In this lecture, we introduce Seidel’s algorithm [3] to solve linear programs with n constraints in dimension d, when the dimension is small. The expected running time of Seidel’s algorithm is O(d!n), i.e. it is strongly polynomial for fixed dimension d (strongly, since it does not depend on the size of the input coefficients). Then, we use Seidel’s algorithm to develop a randomized convex-hull algorithm in an arbitrary dimension d which is the best possible when d ≥ 4. 1 Linear Programming in Fixed Dimension In this section, we fix the dimension d. We wish to find a strongly-polynomial time algorithm to solve linear programming. 1.1 Seidel’s Algorithm Let H be a set of n inequalities. Each inequality corresponds to a half-space h determined by a hyperplane. Let LP (H) be the linear program that minimizes cT x subject to the constraints: d x ∈ h, x ∈ R . h∈H To make the description of the algorithm simpler, we make the following two assumptions: 1. Bounded: the feasible region is bounded, i.e. there exists M such that, for any feasible x, −M ≤ xi ≤ M for all i = 1, 2, . . . , d. This assumption can be enforced by ficticiously imposing a large bounding box, and whenever one of the inequalities of this bounding box is tight at optimum, we know that the linear program