Rozproszone algorytmy aproksymacyjne w analizie własności grafowych
Loading...
Date
2010-06-14T09:53:39Z
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Distributed Approximation Algorithms in the analysis of graph properties
Abstract
Przez ostatnie kilkanaście lat zauważyć można znaczący wzrost zainteresowania algorytmami rozproszonymi. Powodem jest zastosowanie ich w wielu praktycznych zagadnieniach informatyki. Celem rozprawy doktorskiej jest przedstawienie i omówienie deterministycznych rozproszonych algorytmów aproksymacyjnych rozwiązujących podstawowe problemy grafowe, takie jak konstrukcja: minimalnego zbioru dominującego, największego zbioru niezależnego, minimalnego pokrycia wierzchołkowego, największego skojarzenia oraz pakowania grafów. Modelem obliczeń przeze mnie rozważanym jest tzw. model Local. W Rozdziale 2 opisany jest algorytm rozwiązujący problem pakowania grafu G=(V,E) w planarnym grafie H. Zwracane rozwiązanie jest dowolnie dobrą aproksymacją problemu, a złożoność czasowa algorytmu wynosi O(logk|V|). Z praktycznego punktu widzenia zastosowanie znajdują również algorytmy działające w znacząco krótszym czasie, jednak o dużo gorszym współczynniku aproksymacji. Podejście to przedstawiono w Rozdziale 3, gdzie opisane zostały algorytmy działające w czasie O(1). Konstruują one (2 + ε)-aproksymację minimalnego pokrycia wierzchołkowego, w grafach o ograniczonym stopniu, o ograniczonej lesistości. W Rozdziale 4 opisane zostały algorytmy działające w czasie O(log*n). Zwracają one przybliżone rozwiązanie problemów: minimalnego zbioru dominującego, największego skojarzenia oraz największego ważonego zbioru niezależnego w grafach planarnych. Współczynnik aproksymacji wynosi (1 ± ε). Ponadto z twierdzenia udowodnionego w ostatnim Rozdziale 5 wynika, że algorytmy te są optymalne.
Over the past several years there has been growing interest in designing distributed algorithms. It has been motivated by their practical applications in various areas of Computer Science. This thesis is devoted to deterministic distributed approximating algorithms for solving fundamental graph problems such as constructing: minimal dominating set, maximal independent set, minimum vertex cover, maximum matching and graph packing. For all algorithms I consider the synchronous, message-passing model of computations.First, in Chapter 2, we propose an algorithm solving the problem of packing a given graph H into a planar graph G. The algorithm returns an approximate solution with an approximating factor arbitrary close to one and its time complexity is of order O(logkn), where n corresponds to the number of vertices of the input graph G. It turns out that often poly-logarithmic time complexity is still unacceptable. In such situations algorithms with much worse solution, but with constant time complexity are taken into account. This issue is addressed in Chapter 3, where algorithms that produce a (2 + ε)-approximation of the minimum vertex cover problem in bounded degree graphs or graphs of bounded arboricity are presented. In the next chapter further algorithms for planar graphs with sub-logarithmic time complexity are given. They provide solutions with an (1 ± ε)-approximation factor to the following problems: the MDS, the MM and the MWIS. All these procedures terminate in log* n steps. Moreover, in the last chapter of the thesis the results are complemented with the lower bound which proves the optimality of these algorithms
Over the past several years there has been growing interest in designing distributed algorithms. It has been motivated by their practical applications in various areas of Computer Science. This thesis is devoted to deterministic distributed approximating algorithms for solving fundamental graph problems such as constructing: minimal dominating set, maximal independent set, minimum vertex cover, maximum matching and graph packing. For all algorithms I consider the synchronous, message-passing model of computations.First, in Chapter 2, we propose an algorithm solving the problem of packing a given graph H into a planar graph G. The algorithm returns an approximate solution with an approximating factor arbitrary close to one and its time complexity is of order O(logkn), where n corresponds to the number of vertices of the input graph G. It turns out that often poly-logarithmic time complexity is still unacceptable. In such situations algorithms with much worse solution, but with constant time complexity are taken into account. This issue is addressed in Chapter 3, where algorithms that produce a (2 + ε)-approximation of the minimum vertex cover problem in bounded degree graphs or graphs of bounded arboricity are presented. In the next chapter further algorithms for planar graphs with sub-logarithmic time complexity are given. They provide solutions with an (1 ± ε)-approximation factor to the following problems: the MDS, the MM and the MWIS. All these procedures terminate in log* n steps. Moreover, in the last chapter of the thesis the results are complemented with the lower bound which proves the optimality of these algorithms
Description
Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej
Sponsor
Keywords
algorytmy, algorithms, grafy, graphs, rozproszone obliczenia, distributed computing, aproksymacja, approximation