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. A lower bound on the number of steps used by this algorithm is given by the now-disproved Hirsch conjecture. The criss-cross algorithm (15[1])runs similarly to this algorithm, except it skips one of its two phases. This algorithm has worst-case (-5[1])exponential time, as shown by a slightly perturbed cube named (15[1])for (*) Klee and Minty. (10[1])This algorithm stores a set of basic variables and repeatedly pivots in new variables to improve a basic feasible solution. Geometrically, 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

Buzzes

Summary