Algoritmi za problem maksimalnog reza

undergraduate thesis

• Title (english): Algorithms for maximum cut problem
• Author: Jana Perak
• Mentor: Lana Horvat Dmitrović (mentor)
• Committee member: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Committee member: Ana Žgaljić Keko (član povjerenstva)
• Committee member: Mate Puljiz (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom završnom radu proučili smo problem maksimalnog reza. Uveli smo osnovne pojmove o grafu te smo vidjeli da je problem maksimalnog reza NP težak problem. Naveli smo algoritam iscrpne pretrage koji daje točnu vrijednost reza ali za mali broj vrhova te smo naveli i neke algoritme koji ne daju točnu vrijednost reza ali ju dobro aproksimiraju. Najprije je opisan slučajni algoritam, zatim algoritam lokalne pretrage i na kraju Goemans- Williamsonov algoritam, najbolji algoritam za rješavanje problema maksimalnog reza. Na kraju je prikazana implementacija algoritama iscrpne pretrage i Goemans-Williamsonovog algoritma, te je dana usporedba rješenje, uz vizualizaciju rješenja.

Abstract (english)

In this paper we studied the maximum cut problem. We introduced the basic notions of graphs and saw that the maximum cut problem is an NP-hard problem. We listed a greedy search algorithm that gives the exact value of the cut, but only for a small number of the vertices, and we also listed some algorithms that do not give the exact value of the cut, but approximate them well. First, the randomized algorithm is described, then the local search algorithm, and finally the Goemans-Williamson algorithm, the best algorithm for solving the maximum cut problem. At the end, the implementation of the greedy algorithm and the Goemans-Williamson algorithm is presented, and a comparison of the solutions is given, along with a visualization of the solutions.

• Keywords: maksimalni rez
• Keywords (english): maximum cut
• Language: croatian
• URN:NBN: urn:nbn:hr:168:058478
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:27:25