Seminar za teorijsko računarstvo i Seminar za matematičku logiku i osnove matematike
lokacija:
PMF Matematički odsjek
vrijeme:
13.11.2023 - 17:15 - 19:00
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.
