Problem maksimalnog težinskog nezavisnog skupa u grafu

master's thesis

• Title (english): The maximum weight independent set problem in a graph
• Author: Juraj Brigljević
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Goran Igaly (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Committee member: Zrinka Franušić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: NP-težak problem optimizacije; problem maksimalne težinske klike; maksimalni težinski vršni pokrivač; BHOSLIB; DIMACS
• Keywords (english): NP-hard optimization problem; maximum weight clique problem; the maximum weight vertex cover problem; BHOSLIB; DIMACS
• Language: croatian
• URN:NBN: urn:nbn:hr:217:516468
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-01-30 12:10:01