Poziv na predavanje Brzi aproksimacijski algoritmi za frakcionalni problem pakiranja i pokrivanja
Odjel za matematiku Sveučilišta Josipa Jurja Strossmayera u Osijeku organizira predavanje Brzi aproksimacijski algoritmi za frakcionalni problem pakiranja i pokrivanja (Fast approximation algorithms for Fractional Packing and Covering Linear Programs)
NAJAVA – Predavanje će se održati u srijedu, 25. ožujka 2015. godine s početkom u 12 sati u predavaonici broj 2 na Odjelu za matematiku Sveučilišta Josipa Jurja Strossmayera u Osijeku (Trg Ljudevita Gaja 6).
Predavanje će održati:
- Slobodan Jelić, asistent, Odjel za matematiku Sveučilišta Josipa Jurja Strossmayera u Osijeku
[br]
[br] Tijekom predavanja izložit će se ideja sekvencijalne sasvim polinomijalne aproksimacijske sheme Koufogiannakisa i Younga za frakcionalne probleme pakiranja i pokrivanja. Posebna pažnja posvetit će se adaptaciji ovog algoritma na paralelni način računanja koji podržavaju moderne NVidia grafičke kartice s CUDA arhitekturom. Umjesto povećavanja vrijednosti jedne varijable u primalu (maksimizacijski problem) i jedne varijable u dualu (minimizacijski problem), povećat će se nekoliko slučajno izabranih varijabli. Dio doprinosa odnosi se i na deterministički način povećavanja više varijabli u primalu i dualu istovremeno, što se pokazalo prihvatljivijim pristupom prilikom paralelizacije. Iako istovremeno povećavanja velikog broja varijabli zahtjeva više vremena po iteraciji, takav pristup osigurava bržu konvergenciju primalnog i dualnog rješenja ka optimalnom, što smanjuje ukupan broj iteracija algoritma.