Seminar za teorijsko računarstvo
U okviru Seminara za teorijsko računarstvo, u ponedjeljak 18. siječnja 2021. u 15:00 sati
Robert Manger i Ana Klobučar održat će predavanje pod naslovom:
"Rješavanje robusnih problema težinskog nezavisnog skupa na stablima i uz intervalnu nesigurnost".
Sažetak: Proučavamo robusne varijante problema maksimalnog težinskog nezavisnog skupa na stablima. Nesigurnost (neodređenost) težina vrhova prikazana je intervalima. Najprije pokazujemo da se max-min varijanta problema može riješiti u linearnom vremenu. Zatim dokazujemo da je min-max regret varijanta NP-teška. Na kraju predlažemo i testiramo dva međusobno povezana aproksimacijska algoritma za rješavanje min-max regret varijante.
Predavanje će se održati u obliku telekonferencije (on-line) na platformi Zoom. Podaci za spajanje:
Link: https://zoom.us/j/98709088906?pwd=MDNsSHRqaTBTcUNPRDNFaWY5WXgvZz09
Meeting ID: 987 0908 8906
Pozivaju se svi članovi seminara kao i ostali zainteresirani da se pridruže.
Robert Manger.