TU CE GSC CE People at the Graduate School CE Students Alexander V. Hopp The complexity of Zadeh's pivot rule

The complexity of Zadeh's pivot rule

Zadeh's Least-Entered pivot rule is a memorizing pivot rule applicable to a wide range of algorithms. The most prominent example is the Simplex Algorithm since, for over thirty years, it was not clear if Zadeh's pivot rule might be the first polynomial time pivot rule for the Simplex Algorithm. In general, the worst-case running time of algorithms using Zadeh's pivot rule is not exhaustively and satisfyingly researched yet, though it attracted more attention through the last years.

Following the work of Friedmann (IPCO, 2011), the goal of this project is to further investigate the worst-case running time of algorithms using Zadeh's pivot rule. We already corrected the work of Friedmann (Disser&Hopp, IPCO, 2019) as a first step towards further understanding the design of general worst-case examples. The main goal of the project is to provide an improved exponential lower bound for several algorithms using Zadeh's pivot rule.

This class includes the discrete Strategy Improvement Algorithm for solving parity games and the Simplex Algorithm. This result and the insights on the general structure of worst-case examples for Zadeh's pivot rule might then be used to prove exponential lower bounds for even more algorithms using Zadeh's pivot rule and other pivot rules.

Alexander V. Hopp

M.Sc.

Address: | Dolivostr. 15 |

D-64293 Darmstadt | |

Germany | |

Phone: | +49 6151 16 - 24395 |

Fax: | +49 6151 16 - 24404 |

Office: | S4|10-227 |

Email: | |