Eksperimentalno ovrednotenje algoritmov za problem razmeščanja centrov : magistrsko delo

Eleršič, Miha (avtor), Mihelič, Jurij (mentor)

V magistrskem delu predstavimo in implementiramo algoritme za reševanje problema razmeščanja centrov. Osredotočimo se na obstoječe približne algoritme. Razvijemo tudi nov natančen algoritem, ki je občutno hitrejši od izčrpnega preiskovanja. Za potrebe testiranja implementiramo generator naključnih testnih primerov za različne strukture grafov. Ta podpira generiranje naključnih povezanih grafov, dvodimenzionalnih mrež in brezlestvičnih omrežij. Našo implementacijo približnih algoritmov preverimo na standardni knjižnici testnih primerov in na primerih, generiranih z našim generatorjem. Za približne algoritme primerjamo razmerje med časom izvajanja in kakovostjo rešitve.

• Jezik: Slovenski jezik
• Ključne besede: algoritmi na grafih, kombinatorična optimizacija, razmeščanje centrov
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko ; FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2018
• PID: 20.500.12556/RUL-103882
• UDK: 519.8
• COBISS.SI-ID: 18455129
• Datum objave v RUL: 28.09.2018

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Experimental Evaluation of Algorithms for the Vertex k-center Problem

Izvleček

In this thesis we present and implement algorithms for the $k$-center problem. We focus on existing heuristic algorithms. We also develop a new exact algorithm and show its superiority over the exhaustive enumeration. For testing purposes we implemented a random graph generator. It can generate random connected graphs, two-dimensional grids and scale-free networks. Our implementation of algorithms was tested on the standard test suite and the graphs generated by our generator. We also compare the ratio between computation time and result quality of heuristic algorithms.

• Ključne besede: graph algorithms, combinatorial optimization, vertex k-center