Problem maksimalnog težinskog nezavisnog skupa u grafu

diplomski rad

• Naslov (engleski): The maximum weight independent set problem in a graph
• Autor: Juraj Brigljević
• Mentor: Robert Manger (mentor)
• Član povjerenstva: Robert Manger (predsjednik povjerenstva)
• Član povjerenstva: Goran Igaly (član povjerenstva)
• Član povjerenstva: Dijana Ilišević (član povjerenstva)
• Član povjerenstva: Zrinka Franušić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Problem maksimalnog težinskog nezavisnog skupa u grafu jedan je NP-težak problem optimizacije. On ima primjene u stvarnome svijetu, koje zahtijevaju brze algoritme koji pronalaze kvalitetna rješenja. Osim toga, u bliskoj je vezi s problemima maksimalne težinske klike i maksimalnog težinskog vršnog pokrivača. U ovome radu definirani su navedeni problemi i iskazane su njihove međusobne veze. Proučena je njihova vremenska složenost u teorijskom smislu i iskazani su relevantni rezultati. Kako je problem maksimalnog težinskog nezavisnog skupa NP-težak, u njegovu rješavanju posežemo za heuristikom kako bismo na brz način pronašli kvalitetna rješenja u općenitom slučaju, a proučavamo i kako se problem može egzaktno riješiti u slučaju stabla. Heuristika koju smo proučili temeljena je na dvjema paradigmama: ponavljanom lokalnom pretraživanju i varijabilnim spustom uz korištenje susjedstava. Ponavljano lokalno pretraživanje heuristika je u kojoj se trudimo pronaći sve bolje rješenje pretraživanjem neke lokalne okoline trenutnoga rješenja. Ideja je da se na taj način trudimo doseći lokalni optimum pod pretpostavkom određene neprekidnosti područja pretraživanja. Kako na taj način možemo zapeti u lokalnom optimumu, u navedeni postupak uključujemo korak perturbacije koji nastoji pronaći ostale lokalne optimume. Da bismo uspjeli efikasno istražiti blizinu trenutnoga rješenja, potreban nam je dobar pojam bliskih rješnja. Iz tog razloga posežemo varijabilnom spustu uz korištenje susjedstava, u kojemu definiramo par susjedstava unutar kojih tražimo bolja rješenja od trenutnoga. Navedeni algoritam je implementiran i testiran na bazama podataka BHOSLIB i DIMACS, na kojima je uočeno da daje kvalitetna rješenja u izrazito malome vremenu.

Sažetak (engleski)

The maximum weight independent set is an NP-hard optimization problem. It has some real-world applications, which require quick algorithms that find quality solutions. Also, it is in a close relationship with the maximum weight clique problem and the maximum weight vertex cover problem. In this thesis, the listed problems are defined and their relationships are expressed and proven. Their time complexity is studied in a theoretical sense and the relevant results are expressed. Since the maximum weight independent set is NP-hard, quality solutions in the general case are found by solving it in a heuristic approach, while the problem is also solved exactly in the case of trees. The studied heuristic is based on two paradigms: iterated local search and variable neighborhood descent. Iterated local search is a heuristic in which we try to find better solutions by searching the local neighborhood of the current solution. The idea is that by doing so we try to reach a local optimum under the assumption of continuity of the search area. Since this can lead to the algorithm getting stuck in a local optimum, a perturbation step is included which attempts to find other local optima. In order to efficiently search the vicinity of the current solution, a good notion of similar solutions is required. For that goal, variable neighborhood descent is defined alongside two notions of neighborhoods which are deemed to contain similar solutions. The algorithm is implemented and tested on the BHOSLIB and DIMACS databases, where it is observed that it quickly finds quality solutions.

• Ključne riječi: NP-težak problem optimizacije; problem maksimalne težinske klike; maksimalni težinski vršni pokrivač; BHOSLIB; DIMACS
• Ključne riječi (engleski): NP-hard optimization problem; maximum weight clique problem; the maximum weight vertex cover problem; BHOSLIB; DIMACS
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:516468
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar računarstva i matematike (univ. mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-01-30 12:10:01