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

Eleršič, Miha (author), 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.

• Language: Slovenian
• Keywords: algoritmi na grafih, kombinatorična optimizacija, razmeščanje centrov
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics; FRI - Faculty of Computer and Information Science
• Year: 2018
• PID: 20.500.12556/RUL-103882
• UDC: 519.8
• COBISS.SI-ID: 18455129
• Publication date in RUL: 28.09.2018

Secondary language

• Language: English
• Title: Experimental Evaluation of Algorithms for the Vertex k-center Problem

Abstract

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.

• Keywords: graph algorithms, combinatorial optimization, vertex k-center