Семинар за рачунарство и примењену математику, 23. април 2024.

• 19. Април, 2024
• Коментари (0)

Наредни састанак Семинара биће одржан у уторак, 23. априла 2024, у сали 301ф Математичког института САНУ са почетком у 14.15.

Предавачи: Стефан Капунац, Математички факултет, Универзитет у Београду

Наслов предавања: ПРОБЛЕМ ТЕЖИНСКЕ ТОТАЛНЕ ДОМИНАЦИЈЕ СА ПРИМЕНАМА

Апстракт: Проблем тежинске тоталне доминације (WTDP) је практично проширење добро познатог проблема тоталне доминације. Најефикаснији приступи у литератури за решавање овог проблема се базирају на гранању са ограничавањем или генетском алгоритму.

У излагању ће бити представљена метода променљивих околина (VNS) за решавање овог проблема. VNS је опремљен пажљиво дизајнираном функцијом прилагођености која омогућава евалуацију како допустивих, тако и недопустивих решења, што омогућава темељну претрагу обећавајућих региона простора претраге. Метод такође користи две локалне претраге првог побољшања.

Делотворност VNS-а је демонстрирана на широком спектру референтних скупова инстанци поређењем са три конкурентна метода из литературе.
На инстанцама мале до средње величине (до 100 чворова), квалитет VNS решења се у скоро свим случајевима подудара са квалитетом оптималних решења (134 од 135). На средњим до великим инстанцама, VNS је надмашио све упоредне алгоритме у смислу квалитета решења, што је потврђено статистичким тестовима хипотеза.

Биће представљена и потенцијална примена WTDP-а за убрзавање ширења информација на друштвеним мрежама. Експерименти су потврдили да се ширење информација убрзава када су информисани чворови (они који су иницијално обавештени о вести/трачу итд.) постављени као решења WTDP-а добијена помоћу VNS-а. Иако је предложени метод успешно примењен на узорцима стварних друштвених мрежа до 81 хиљаде чворова и 1.34 милиона грана, даља истраживања могла би унапредити метод како би се користио на потпуним (неузоркованим) скуповима података друштвених мрежа.


Напомена: Регистрациона форма за учешће на Семинару је доступна на линку:
https://miteam.mi.sanu.ac.rs/call/wnz6oyxsQsy29LfJA/MjQ__eH607WeAL9X7IFtUI98xdQQgVkp-ljiEKPPfXr

Уколико желите само да пратите предавање без могућности активног учешћа, пренос је доступан на линку:
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So