Linear-programming algorithms Algorithms for the general problem Simplex methods--practical, but worst-case exponential time Ellipsoid algorithm- polynomial time, but slow in practice Interior-point methods- polynomial time and competes with simplex Feasibility problem: No optimization criterion Just find x such that ax< b In general, just as hard as ordinary LP c 2001 by Charles E Leiserson Introduction to Agorithms Day31L1818© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.18 Linear-programming algorithms Algorithms for the general problem • Simplex methods — practical, but worst-case exponential time. • Ellipsoid algorithm — polynomial time, but slow in practice. • Interior-point methods — polynomial time and competes with simplex. Feasibility problem: No optimization criterion. Just find x such that Ax ≤ b. • In general, just as hard as ordinary LP