is Íslenska en English

Lokaverkefni (Meistara)

Háskóli Íslands > Verkfræði- og náttúruvísindasvið > Meistaraprófsritgerðir - Verkfræði- og náttúruvísindasvið >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/23105

Titill: 
  • Titill er á ensku A First Attempt on the Distributed Prize Collecting Steiner Tree Problem
Námsstig: 
  • Meistara
Útdráttur: 
  • Útdráttur er á ensku

    The goal of this work is to design and simulate a distributed algorithm to solve a novel variant of the Price Collecting Steiner Tree (PCST) problem, where nodes are computing entities with only local information and communication abilities. Our approach is to study existing techniques for the centralized PCST, such as the Primal-Dual Integer Program given by Goemans and Williamson (GW-algorithm), and distributed algorithms for the Minimum Spanning Tree (MST) and minimum Steiner Tree Problem. None of the above adapts easily to our problem. However, we introduce a simple MST-based heuristic that runs on a custom Python simulator. Our heuristic does not guarantee any approximation factor of the optimal solution, but it proved well against benchmark instances found in literature for which it was able to find solutions within the approximation guarantee of the GW-algorithm for all but few instances. We also designed an adaptation of the original GW-algorithm to our distributed model. Though it follows the sequential steps of the original algorithm, this is the first distributed algorithm with an approximation guarantee for the PCST. Simulator and algorithms' code is available on a public repository as free software.

  • Í verkefninu er fengist við hönnun og hermun á dreifðu reikniriti til lausnar á nýrri útgáfu af verðlaunasafnandi Steinertrjáa verkefninu (e. Prize Collecting Steiner Tree, PCST), þar sem hnútar hafa reiknigetu og aðeins staðbundna samskiptagetu og upplýsingar um nágranna í neti. Aðferðin byggist á að rannsaka þær aðferðir sem eru nú þegar til fyrir miðstýrðu útgáfuna af PCST, s.s. nykrað heiltölubestunarreiknirit eftir Goemans og Williamson (GW), dreifð reiknirit fyrir minnstu spanntré (e. Minimum Spanning Tree, MST) og lágmörkun á Steinertrjám. Ekkert af eftirtöldum reikniritum aðlagast auðveldlega að dreifðum reikningum. Við kynnum nýja einfalda brjóstvitsaðferð byggða á MST og útfærða í sérstökum hermi í Python. Aðferðin tryggir ekki nálgunarstuðul á bestu lausn en skilar góðum niðurstöðum í viðmiðunarverkefnum sem birt hafa verið og var nálgunarstuðullinn innan við það sem GW reikniritið tryggir í nánast öllum tilfellum. Einnig var GW reikniritið útfært í dreifðri útgáfu. Python hermirinn fyrir dreifð reiknirit og reikniritið sjálft eru gefin út sem frjáls hugbúnaður.

Samþykkt: 
  • 2.10.2015
URI: 
  • http://hdl.handle.net/1946/23105


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
niccolo.pdf1.04 MBOpinnHeildartextiPDFSkoða/Opna