Seminar za teorijsko računarstvo

lokacija: 
PMF Matematički odsjek
vrijeme: 
05.03.2018 - 15:00 - 16:30

U sklopu poslijediplomskog Seminara za teorijsko računarstvo u ponedjeljak
5. ožujka 2018. u 15 sati, predavaonica 104 PMF-MO, Goranka Nogo i njezini
studenti Mihaela Gamulin, Monika Majstorović, Luka Valenta održat će
predavanje pod naslovom:

"Minimizacija najduljeg brida u k-Steinerovom stablu".

Sažetak: Problem minimizacije najduljeg brida (eng. bottleneck) u
k-Steinerovom stablu za zadane točke i prirodan broj k jest problem
pronalaska razapinjućeg stabla čiji su čvorovi zadane točke i najviše k
dodatnih točaka, koje nazivamo Steinerove točke, tako da je duljina
bottlenecka minimalna. Opisani problem je NP-težak. U seminaru se problem
rješava " multi-swarm" optimizacijom, inačicom algoritma roja čestica i
analiziraju rezultati na instancama iz OR-Library. Dobiveni rezultati
uspoređuju se s rezultatima "minimal spanning tree" heuristike koja je
trenutno jedna od najboljih determinističkih heuristika za ovaj problem.

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

Robert Manger

Share this