ÍslenskaenEnglish

Aðilar að Skemmunni

Leit eftir:


LokaverkefniHáskólinn í Reykjavík>Tölvunarfræðideild>Doktorsritgerðir>

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

Titlar
  • en

    Approximation algorithms for independent set problems on hypergraphs

  • Nálgunarreiknirit fyrir óháð mengi í ofurnetum

Útgáfa
Desember 2009
Útdrættir
  • en

    This thesis deals with approximation algorithms for the Maximum Independent Set and the Minimum Hitting Set problems on hypergraphs. As a hypergraph is a generalization of a graph, the question is whether the best known approximations on graphs can be extended to hypergraphs.
    We consider greedy, local search and partitioning algorithms. We introduce a general technique, called shrinkage reduction, that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to prove approximation ratios for greedy and local search algorithms for the MaximumWeak Independent Set problem on weighted and unweighted bounded-degree hypergraphs. For the weighted case we improve bounds using a simple partitioning algorithm. We also consider two variations of the max-greedy algorithms for the Maximum Strong Independent Set problem.
    We describe an SDP-based approach for the Maximum Weak Independent Set problem on bounded-degree hypergraphs. Our approach is to use semidefinite technique to sparsify a given hypergraph and then apply combinatorial algorithms to find a large independent set in the resulting sparser instance. Using this approach we obtain the first performance ratio that is sublinear in terms of the maximum or average degree of the hypergraph. We extend this result to the weighted case and give a similar bound in terms of the average weighted degree in a hypergraph, matching the best bounds known for the special case of graphs.
    We present several randomized and deterministic algorithms for the Maximum Weak Independent Set problem in a semi-streaming model. All our semi-streaming algorithms require only one pass over the stream and most of them resemble on-line algorithms in maintaining a feasible solution at all times. We introduce the on-line minimal space semi-streaming model and give lower and upper bounds for deterministic and randomized algorithms in this model.

  • Þessi ritgerð fjallar um bestunaraðferðir fyrir ofurnet, eða nánar tiltekið um nálgunarreiknirit fyrir verkefnin stærsta óháða mengi (e. maximum independent set) og minnsta skurðmengi (e. minimum hitting set) á ofurnetum. Ofurnet eru útvíkkun á netum, og því er spurningin hvort þekktar nálgunaraðferðir fyrir net megi einnig útvíkka fyrir ofurnet.
    Við skoðum fyrst reiknirit sem byggja á gráðugu vali, staðbundinni bestu, og skiptingu. Við kynnum nýja almenna smækkunaraðferð sem gerir okkur kleift að yfirfæra nálgunarniðurstöður fyrir net sem byggja á gráðugu vali og staðbundinni bestun yfir á vegin og óvegin ofurnet með takmarkaða hámarksgráðu. Fyrir vegin ofurnet bætum við nálgunina enn frekar með því að nota einfalda skiptingaraðferð. Við skoðum einnig tvær útgáfur af gráðugri aðferð til að finna stærsta sterka óháð mengi í ofurneti.
    Við lýsum síðan aðferð sem beitir hálfákveðinni bestun til að gera ofurnetið fyrst rýrara og nýtir síðan samtektareiknirit á rýra netið. Með þessari aðferð fáum við út fyrstu nálgunarniðurstöður sem vaxa hægar en línulega sem fall af hámarks- eða meðaltalsgráðu ofurnetsins. Við útvíkkum þessar niðurstöður fyrir vegin ofurnet, og fáum sambærilegar niðurstöður sem fall af veginni meðalgráðu.
    Í síðasta hluta ritgerðarinnar snúum við okkur að bunuvinnslu (e. Streaming algorithms). Þá koma leggir netsins í runu, en reikniritið getur aðeins geymt lítinn hluta netsins. Við leiðum út ýmis slembin og ákvörðunarbundin reiknirit fyrir stærsta óháða mengi í netum og ofurnetum. Allar aðferðirnar krefjast aðeins einnar yfirferðar yfir strauminn og eru flestar raðbundnar (e. online) að því leyti að gildri lausn er sífellt viðhaldið. Við kynnum nýtt líkan fyrir bunuvinnslu á netum sem krefst raðbundinnar vinnslu með lágmarks plássþörf, og gefum efri og neðri mörk fyrir reiknirit í því líkani.

Birting
24.1.2011


Skrár
NafnRaðanlegtStærðRaðanlegtAðgangurRaðanlegtLýsingRaðanlegtSkráartegund
PhD_Elena-Losievskaja.pdf640KBOpinn Heildartexti PDF Skoða/Opna