Question

Applying policy iteration to a Markov decision process one state at a time is equivalent to performing this algorithm. The technique of smoothed analysis was originally developed by Spielman and Teng to explain this algorithm’s behavior. (-5[1])A lower bound on the number of steps used by this algorithm is given by the now-disproved Hirsch conjecture. The criss-cross algorithm runs similarly to this algorithm, except it skips one of its two phases. This algorithm has worst-case exponential time, as shown by a slightly perturbed cube named for (*) Klee and Minty. (10[1])This algorithm (10[1])stores a set of basic variables and repeatedly pivots in new variables to improve a basic feasible solution. (10[1])Geometrically, (10[1])this algorithm can be viewed as moving along adjacent vertices of a polytope until an extremal one is reached. For 10 points, name this fast algorithm developed by George Dantzig for linear programming. ■END■ (10[1])

Back to tossups