Seminar za teorijsko računarstvo i Seminar za matematičku logiku i osnove matematike

Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 13. studenoga 2023. godine u 17:15 sati, u predavaonici 201, Juraj Brigljević će održati predavanje

Rješavanje problema maksimalnog težinskog nezavisnog skupa

Sažetak: Problem maksimalnog težinskog nezavisnog skupa (MWIS) spada u područje diskretne optimizacije na grafovima. S obzirom da je riječ o NP-teškom problemu, opravdano je korištenje heuristika za njegovo rješavanje u općenitom slučaju. Heuristika koju smo proučili utemeljena je na dvjema paradigmama: ponavljanom lokalnom pretraživanju (ILS) odnosno varijabilnom spustu uz korištenje susjedstava (VND). Testiranjem na bazama podataka BHOSLIB i DIMACS uvjerili smo se da navedena heuristika može izrazito brzo pronaći dobra rješenja, a vrlo često i optimalna odnosno najbolja poznata rješenja. Osim heuristike ILS-VND, koja radi na općenitim grafovima, proučili smo postoji li bolje rješenje za jednu posebnu vrstu grafova, a to su stabla. Pokazalo se da se pomoću paradigme dinamičkog programiranja može definirati egzaktni algoritam koji rješava MWIS problem na stablima u linearnom vremenu s obzirom na broj vrhova.

Zoom link: https://zoom.us/j/97325200710?pwd=b2g1ZCtSTjk1dmRQZVVYWTUwOFdMZz09