Úloha lineárního programování v rovině

Formulace problému, možná řešení - prázdný průnik (infeasible), má řešení (feasible), neomezený lineární program ve směru vektoru c. Přírustkový algoritmus, lemma o nalezení bodu maxima, řešení jednodimenziálního problému v lineárním čase, algoritmus 2DboundedLP na stranách 83 a 84 knihy. Nalezení maxima v čase O(n²). Proto musíme použít náhodnostní algoritmus, ten dává očekávaný čas O(n). Algoritmus RandomPermutation, zdůvodnění pomocí střední hodnoty náhodné veličiny.

Viz strana 16 souboru

Tabule z 6. přednášky

Detailní, přesto dobře čitelný popis algoritmu