Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 20. svibnja 2024. godine u 17:15 sati, u predavaonici 201, Robert Manger će održati predavanje

 

Rješavanje problema dvostruke rimske dominacije s minimalnom cijenom

 

Sažetak: Dvostruka rimska dominacija (DRD) je optimizacijski problem koji se zadaje na neusmjerenom grafu. Formalno se opisuje kao pridruživanje težina vrhovima grafa u skladu s određenim pravilima. Neformalno, problem se može interpretirati kao raspoređivanje davatelja usluge (npr. vojnih jedinica, vatrogasnih brigada ili bolničkih kola) po odabranim lokacijama unutar nekog geografskog područja. Pritom cjelokupna usluga (tj. odgovor na neprijateljske napade, požare ili hitne medicinske slučajeve) treba biti uspostavljena na najjeftiniji način, s time da još uvijek bude osigurana tzv. "dvostruko-rimska" razina njezine dostupnosti i pouzdanosti. Standardna verzija DRD iz postojeće literature poistovjećuje ukupan trošak s ukupnim brojem potrebnih davatelja usluge.

 

U ovom radu razmatra se nova verzija DRD zasnovana na minimalnoj cijeni, koja je općenitija i realističnija od standardne verzije. Polazi se od pretpostavke da se stvarni troškvi davanja usluge mogu razlikovati od lokacije do lokacije. Dakle, formalno govoreći, svakom vrhu u grafu zadana je cijena koja se interpretira kao cijena držanja jednog davatelja usluge na odgovarajućoj lokaciji.

 

U radu se najprije primjećuje da je razmatrani DRD problem s minimalnom cijenom NP-težak, i to ne samo za općenite grafove nego također i za mnoge posebne klase grafova. Dalje, konstruira se algoritam dinamičkog programiranja koji pokazuje da se problem ipak može riješiti u linearnom vremenu ako razmatrani graf ima oblik stabla. Na kraju, kao rješenje za općenite grafove, predlaže se heuristika zasnovana na pohlepnom pristupu i lokalnom traženju.

 

Zoom link: https://zoom.us/j/91249923788?pwd=NmlLcVVuNU5LZDhXMGhEYjd1VXEvQT09

 

Meeting ID: 912 4992 3788