Primjena semidefinitnog programiranja na probleme bojanja grafa

diplomski rad

• Naslov (engleski): Semidefinite programming applied to graph colouring problems
• Autor: Fran Bedić
• Mentor: Josipa Pina Milišić (mentor)
• Član povjerenstva: Josipa Pina Milišić (predsjednik povjerenstva)
• Član povjerenstva: Tomislav Burić (član povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Semidefinitno programiranje bavi se minimizacijom linearne funkcije uz ograničenja da je afina kombinacija matrica pozitivno semidefinitna. U ovom radu proučavali smo primjenu semidefinitnog programiranja na probleme bojanja grafa. Detaljno su opisani semidefinitni programi te osnovne poteškoće koje se javljaju prilikom rješavanja semidefinitnih programa. Opisani su i algoritmi koji se mogu koristiti za rješavanje semidefinitnh programa. Nadalje, u drugom dijelu rada opisani su osnovni pojmovi vezani za teoriju grafova i bojanje grafa te je iznesena relaksacija problema bojanja grafa u smislu vektorskog odnosno matričnog bojanja grafa, a naposljetku kao i problem semidefinitnog programiranja. Na kraju smo opisali algoritam bojanja grafa temeljen na semidefinitnom programiranju te smo demonstrirali i prokomentirali rezultate algoritma na konkretnoj implementaciji.

Sažetak (engleski)

Semidefinite programming minimizes a linear function with the constraint that the afine matrix combination is positively semidefinite. In this paper we've studied the application of semidefinite programming in the graph coloring problem. A detailed description of semidefinite programs was given along with the difficulties that occur during their solving. Some algorithms that are useful for solving semidefinite programs were also covered. Furthermore, the second part of the paper describes the basic concepts of graph theory and graph coloring. A relaxation of the coloring problem is given by associating it with vector or matrix graph coloring and, finally, with the semidefinite programming problem. In the end we described a graph coloring algorithm based on semidefinite programming and we demonstrated and discussed its performance on a concrete implementation.

• Ključne riječi: semidefinitno programiranje; bojanje grafova; konveksna optimizacija; kombinatorna optimizacija
• Ključne riječi (engleski): semidefinite programming; graph coloring; convex optimization; combinatorial optimization
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:613364
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 11:46:23