Układy nierówności liniowych można rozwiązywać wielomianowo. Na tych zajęciach
spokojnie i dość szczegółowo omówimy takie zagadnienia zwiazane z programami
liniowymi jak: * LP duality * complementarity slackness * Farkas lemma *
algorytm simplex * metodę elipsoid * separation oracle * rozwiazywanie dużych
(niewielomianowych) instancji * Hirsh conjecture.
Nastepnie omówimy pewne aspekty programowania całkowitoliczbowego: * algorytm
branch and bound * alg. branch and cut * algorytmy wielomianowe dla przypadku
stałej liczby wymiarów * metody oparte o algebraiczne manipulacje na kracie
punktów calkowitoliczbowych * algorytm LLL do redukcji bazy takiej kraty *
problemy shortest latice vector i closest latice vector.
Dodatkowo omówimy zastosowanie programowania liniowego do konstrukcji
algorytmów aproksymacyjnych na przykladzie problemow Facility Location i min
cost Steiner tree.
W czesci kursu poslużymy sie notatkami:
http://homepages.cwi.nl/~lex/files/dict.pdf Bedziemy rownież korzystać z
książki: "Theory of Linear and Integer Programmin", Alexander Shrijver.
Zajęcia będą zakończone egzaminem na ocenę.
