Linear Programming- Randomization and

Abstract. Recent years have brought some progress in the knowledge of the complexity of linear programming in the unit cost model, and the best result known at this point is a randomized `combinatorial ' algorithm which solves a linear program over d variables and n constraints with expected O(d2n + eO(pd log d)