Seminar za teorijsko računarstvo
U okviru Seminara za teorijsko računarstvo, u ponedjeljak 4. studenog 2019. u 15 sati, predavaonica 104 PMF-MO,
Ana Klobučar s Fakulteta strojarstva i brodogradnje Sveučilišta u Zagrebu održat će predavanje pod naslovom:
"Robusne varijante problema maksimalnog težinskog nezavisnog skupa na stablima".
Sažetak: Proučavamo robusne varijante problema maksimalnog težinskog nezavisnog skupa na stablima. Koristimo tri osnovna kriterija robusnosti: apsolutna robusnost, robusna devijacija te relativna robusna devijacija. Također promatramo i općenitije OWA kriterije. Pretpostavljamo da je nesigurnost u pogledu težina vrhova izražena preko eksplicitnog skupa scenarija ili pomoću intervala. Poznato je da je konvencionalni problem na stablima rješiv u polinomijalnom vremenu, no pokazat ćemo da slična tvrdnja ne vrijedi u slučaju robusne optimizacije. Nadalje, predložit ćemo približni algoritam za rješavanje robusnih varijanti problema, koji je specijalno dizajniran za stabla i koji uzima u obzir njihovu strukturu, a zasnovan je na dinamičkom programiranju, evolucijskom računanju i pohlepnom odlučivanju.
Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju ovom predavanju.
Robert Manger