U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak 29. listopada 2018. u 15 sati, predavaonica 104 PMF-MO, Robert Manger i Ana Klobučar održat će predavanje pod naslovom:

 

"Odnos nezavisnih skupova i vršnih pokrivača u kontekstu robusne optimizacije".

 

Sažetak: Ovaj rad bavi se robusnim varijantama problema maksimalnog težinskog nezavisnog skupa odnosno problema minimalnog težinskog vršnog pokrivača. Oba problema zadani su u grafu čiji vrhovi imaju težine. Nesigurnost u težinama vrhova izražena je preko konačnog broja eksplicitno zadanih scenarija. Rad se bavi pitanjem: mora li komplement robusno-optimalnog nezavisnog skupa biti robusno-optimalni vršni pokrivač, i obratno (kao što je to istina za konvencionalne optimume). Pokazuje se da odgovor na ovo pitanje nije jednoznačan te da ovisi o odabranom kriteriju robusnosti.

 

Pozivaju se svi članovi Seminara kao i ostali zainteresirani da prisustvuju ovom predavanju.

 

Robert Manger.