Jak wiadomo, układy nierównoś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 W czesci kursu posluzymy sie
tymi notatkami: 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
