Układy nierowności liniowych można rozwiązywać wielomianowo. Na tych zajęciach
spokojnie i dosc szczegolowo omowimy takie zagadnienia zwiazane z programami
liniowymi jak: * LP duality * complementarity slackness * Farkas lemma *
algorytm simplex * metode elipsoid * separation oracle * rozwiazywanie dużych
(niewielomianowych) instancji * Hirsh conjecture Nastepnie omowily pewne
aspekty programowania calkowitoliczbowego: * algorytm branch and bound * alg.
branch and cut * algorytmy wielomianowe dla przypadku stalej liczby wymiarow *
metody oparte o algebraiczne manipulacje na kracie punktow calkowitoliczbowych
* algorytm LLL do redukcji bazy takiej kraty * problemy shortest latice vector
i closest latice vector.
Dodatkowo omowimy zastosowanie programowania liniowego do konstrukcji
algorytmow aproksymacyjnych na przykladzie problemow Facility Location i min
cost Steiner tree.
W czesci kursu posluzymy sienotatkami:
http://homepages.cwi.nl/~lex/files/dict.pdf Bedziemy rownież korzystać z
książki: "Theory of Linear and Integer Programmin", Alexander Shrijver.
Zajecia beda zakonczone egzaminem na ocene
