Two important discover ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These algo rithms have had a profound effect in combinatorial optimization.