Aproksimacijski algoritmi Osnovne informacije I071 (2+2+0) - 6 ECTS bodova Upoznati studente s temeljnim i naprednim principima u dizajnu aproksimacijskih algoritama za kombinatorne optimizacijske probleme čije je egzaktno rješenje vremenski neefikasno. U ovom predmetu studenti će upoznati tehnike analize težine samog problema, ali i njegove aproksimabilnosti tj. koliko se nekakav kombinatorni problem može efikasno aproksimirati. Upotrebom teorije linearnog i semidefinitnog programiranja razvit će metode kojim se mogu dizajnirati i analizirati aproksimacijski algoritmi. Kroz predmet predstavit će se nekoliko poznatih kombinatornih optimizacijskih problema i njihovi aproksimacijski algoritmi. Sadržaj kolegija možete dohvatiti na sljedećem linku: PDF Nastavnici Osnovna literatura V. Vazirani, Approximation Algorithms, Springer, 2011. D. P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011. Dopunska literatura B. Gaertner, J. Matoušek, Approximation Algorithms and Semidefinite Programming, Springer, 2012. D. Hochbaum, Approximation Algorithms for NP-hard Problems, Course Technology, 1 Ed, 1996. B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2018. C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover publications, 1998. Materijali Materijali su dostupni na internom Teams kanalu kolegija pomoću kojeg se odvija i sva interna komunikacija. Studenti su obvezni registrirati se na Teams kanal kolegija. Šifra kanala kolegija pomoću kojeg se možete pridružiti kolegiju nalazi se u rasporedu.