Seminar za računarstvo i primenjenu matematiku, 23. april 2024.

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

 


 Ostavite vaš komentar 

Komentari(0)

Nažalost nije moguće ostaviti komentar.