Primjena semidefinitnog programiranja na probleme bojanja grafa

master's thesis

• Title (english): Semidefinite programming applied to graph colouring problems
• Author: Fran Bedić
• Mentor: Josipa Pina Milišić (mentor)
• Committee member: Josipa Pina Milišić (predsjednik povjerenstva)
• Committee member: Tomislav Burić (član povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: semidefinitno programiranje; bojanje grafova; konveksna optimizacija; kombinatorna optimizacija
• Keywords (english): semidefinite programming; graph coloring; convex optimization; combinatorial optimization
• Language: croatian
• URN:NBN: urn:nbn:hr:168:613364
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 11:46:23