Seminar za računarstvo i primenjenu matematiku, 23. april 2024.
- 19. April, 2024
- Komentari (0)
Naredni sastanak Seminara biće održan u utorak, 23. aprila 2024, u sali 301f Matematičkog instituta SANU sa početkom u 14.15.
Predavači: Stefan Kapunac, Matematički fakultet, Univerzitet u Beogradu
Naslov predavanja: PROBLEM TEŽINSKE TOTALNE DOMINACIJE SA PRIMENAMA
Apstrakt: Problem težinske totalne dominacije (WTDP) je praktično proširenje dobro poznatog problema totalne dominacije. Najefikasniji pristupi u literaturi za rešavanje ovog problema se baziraju na grananju sa ograničavanjem ili genetskom algoritmu.
U izlaganju će biti predstavljena metoda promenljivih okolina (VNS) za rešavanje ovog problema. VNS je opremljen pažljivo dizajniranom funkcijom prilagođenosti koja omogućava evaluaciju kako dopustivih, tako i nedopustivih rešenja, što omogućava temeljnu pretragu obećavajućih regiona prostora pretrage. Metod takođe koristi dve lokalne pretrage prvog poboljšanja.
Delotvornost VNS-a je demonstrirana na širokom spektru referentnih skupova instanci poređenjem sa tri konkurentna metoda iz literature.
Na instancama male do srednje veličine (do 100 čvorova), kvalitet VNS rešenja se u skoro svim slučajevima podudara sa kvalitetom optimalnih rešenja (134 od 135). Na srednjim do velikim instancama, VNS je nadmašio sve uporedne algoritme u smislu kvaliteta rešenja, što je potvrđeno statističkim testovima hipoteza.
Biće predstavljena i potencijalna primena WTDP-a za ubrzavanje širenja informacija na društvenim mrežama. Eksperimenti su potvrdili da se širenje informacija ubrzava kada su informisani čvorovi (oni koji su inicijalno obavešteni o vesti/traču itd.) postavljeni kao rešenja WTDP-a dobijena pomoću VNS-a. Iako je predloženi metod uspešno primenjen na uzorcima stvarnih društvenih mreža do 81 hiljade čvorova i 1.34 miliona grana, dalja istraživanja mogla bi unaprediti metod kako bi se koristio na potpunim (neuzorkovanim) skupovima podataka društvenih mreža.
Napomena: Registraciona forma za učešće na Seminaru je dostupna na linku:
https://miteam.mi.sanu.ac.rs/call/wnz6oyxsQsy29LfJA/MjQ__eH607WeAL9X7IFtUI98xdQQgVkp-ljiEKPPfXr
Ukoliko želite samo da pratite predavanje bez mogućnosti aktivnog učešća, prenos je dostupan na linku:
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So
Komentari(0)