Seminar za teorijsko računarstvo

lokacija: 
PMF Matematički odsjek
vrijeme: 
04.11.2019 - 15:00 - 17:00

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

Share this