Рачунарски факултет може се похвалити још једним доктором наука. Докторанд Далибор Ристић је 27. октобра 2023. године одбранио своју докторску дисертацију под називом Имплементација метода променљивих околина за решавање П-следећи проблема над скупом чворова графа, пред трочланом комисијом коју су чинили председник др Драган Урошевић и чланови др Филип Марић и др Миланка Гардашевић Филиповић.
Председник комисије др Драган Урошевић представио је присутнима кандидата након чега је Далибор Ристић почео излагање.
У сажетку свог рада Далибор је истакао следеће:
Проблем п-центра је већ дуго предмет интересовања операционих истраживања. Познат је још од средине прошлог века и представља идентификацију локација за постављање п центара, као и њихову доделу корисницима, на такав начин да је максимална удаљеност корисника од додељеног центра минимизована. Постоји много, како егзактних математичких модела, тако и хеуристичких алгоритама који успешно решавају проблем п-центра.
Међутим, временом се поставило питање шта у случају отказа додељеног центра. У последњој декади, као потенцијални одговор на ово питање, представљено је проширење проблема п-центра познато као проблем п- следећег центра. Проблем п-следећег центра представља идентификацију локација за постављање и доделу п центара, али на такав начин да је минимизована максимална сума растојања корисника до најближег центра и растојања између тог и њему најближег центра.
Посебан тип, познат као проблеми над скупом чворова графа, чине проблеми оптималне селекције центара из скупа чворова графа који представљају све кориснике и потенцијалне центре. Постоји мали број чланака и алгоритама који се баве проблемом отказа центра и стога је у дисертацији дефинисано неколико проблема и решења управо из класе проблема ограничених избором центара из скупа чворова графа. Посматрани су проблеми п-следећег, као и п-другог центра који представља идентификацију п од потенцијалних н центара на такав начин да је минимизована максимална сума растојања корисника до најближег и другог најближег центра.
Далибор је на крају дисертације истакао следеће:
У дисертацији, заједно са предложеним решењима, представљено је неколико “п-проблема” над скупом чворова графа који као део свог решења дају одговор и на евентуални отказ додељених центара. Први такав проблем, дефинисан 2015. године у раду [1], назван је п-следећи центар проблем. Представља идентификацију п од потенцијално н центара са циљем минимизације максималне суме растојања корисника до најближег центра и
растојања између тог и њему најближег центра, као заменског центра који преузима улогу опслуживања корисника у случају отказа примарног центра. Сви проблеми су дефинисани на основу општег неусмереног тежинског графа чији чворови представљају кориснике и центре, а тежине грана растојања између њих. Решење проблема представља промоција тачно п од укупно н чворова графа у тзв. центре који функционално опслужују све кориснике, опет позициониране у чворовима графа. У основи, дисертација се бави оптимизационим проблемима, тако да се центри бирају са циљем да одговарајућа растојања међу њима, односно корисницима, буду минимална. Сви посматрани проблеми су НП-тешки и стога су предложена решења као имплементација хеуристичких алгоритама заснованих на генеричком методу променљивих околина.
Честитамо др Далибору Ристићу.
Слике са одбране погледајте у галерији.