Pienen dominoivan joukon etsiminen tasoverkossa hajautetusti

Show full item record

Permalink

http://hdl.handle.net/10138/44925
Title: Pienen dominoivan joukon etsiminen tasoverkossa hajautetusti
Author: Hilke, Miikka
Contributor: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen laitos
Thesis level:
Abstract: Dominoiva joukko D on jonkin verkon solmujen osajoukko siten, että verkon jokainen solmu joko kuuluu D:hen tai on siihen kuuluvan solmun naapuri. Verkon pienimmän dominoivan joukon löytäminen verkossa on NP-kova ongelma. Mikäli algoritmi etsii pienintä joukkoa, jonka koko on x, mutta sen voidaan taata löytävän vain joukon, jonka koko on enintään ax jollakin vakiolla a, kutsutaan tulosjoukkoa oikean ratkaisun a-approksimaatioksi. Rajoitetetussa verkossa voidaan löytää pienimmän dominoivan joukon approksimaatioita nopeasti. Hajautetussa laskennassa verkon solmut ovat rinnakkaisesti toimivia prosessoreita, jotka suorittavat kaikki samaa algoritmia. Vakioaikaisuudella tarkoitetaan hajautetun laskennan kontekstissa sitä, että prosessorit saavat vaihtaa naapuriprosessoriensa kanssa vain vakiomäärän viestejä. Algoritmi palauttaa valmistuttuaan jokaiselle solmulle tulosteen, esimerkiksi tiedon siitä, kuuluuko solmu dominoivaan joukkoon. Tässä tutkielmassa tarkastellaan pienimmän dominoivan joukon vakioaikaisia approksimaatioita tasoverkossa hajautetun laskennan näkökulmasta. Ensiksi tutkielmassa esitellään todistus, että ei ole olemassa hajautettua algoritmia, joka löytäisi (5 − epsilon)-approksimaation pienimmästä dominoivasta joukosta, kun epsilon > 0. Tämän jälkeen todistetaan, että myös tiukempi (7 − epsilon)-approksimaatioalaraja pätee. Lopuksi esitellään hajautettu algoritmi joka löytää ainakin 52-approksimaation pienimmästä dominoivasta joukosta tasoverkossa. Algoritmi käyttää uniikkeja tunnisteita eikä prosessorien välisten viestien kokoja ole rajoitettu. Algoritmin analyysissä yhdistetään Lenzenin et al. (2010) esittämä alkuperäinen analyysi ja Wawrzyniakin (2013) esittämä analyysin toisen osan parannus.
URI: http://hdl.handle.net/10138/44925
Date: 2014-04-17
Discipline: Algorithms and Machine Learning


Files in this item

Total number of downloads: Loading...

Files Size Format View
gradu.pdf 1019.Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record