\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt

Linear programming.

Random sampling algorithm

Must prove claim, that mean $V \le \sqrt{n}$.

Result:

Iterative Reweighting

Get rid of recursion and highest order term.

Idea:

idea: be “softer” regarding mistakes

Mixed algorithm:

Backwards Analysis

Seidel's Randomized incremental algorithm \[ T(n) \le T(n-1,d)+\frac{d}{n}(O(dn)+T(n-1,d-1)) = O(d!n) \]

Also simplifies proof of main theorem:

Hidden Dimension

Idea:

Intuition

Algorithm BasisLP

Intuition:

Enforcing constraints

Hidden dimension

Simplex

The algorithms we studied above are not simplex algorithms

We don't have polynomial, but Kalai gave a subexponential simplex algorithm

Kalai's algorithm

Contrast