Praca doktorska
Miniatura
Pliki
phd.pdf42.32 MB
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Approximation algorithms: new results for stochastic and parameterized problems

Uproszczony widok
dc.abstract.enThis doctoral dissertation is based on 3 articles, which I have written during my PhD studies. They consist of novel results in the theory of approximation algorithms. Two of them concern the subdomain of stochastic optimization, whereas the focus of the last one lies in the intersection of theories of approximation algorithms and parameterized complexity. The results include approximation algorithms for covering problems under data uncertainty. In this setting we consider problems such as Set Cover, where only a part of data is known in advance. The algorithm must construct an assignment encoding a solution for all potential inputs, basing on a probability distribution over input scenarios. Another area is designing mechanisms and auctions, where each player/item can be approached only once and we look for a strategy that would maximize the mechanism's revenue with respect to a given distribution. In the last part I focus on graph problems in which we want to delete a small set of vertices to impose some property of a graph. These results provide significant improvements of approximation coefficients or running time for several problems of this kind.
dc.abstract.plNiniejsza rozprawa doktorska oparta jest na 3 artykułach, które opublikowałem w trakcie studiów III stopnia. Zawierają one nowatorskie wyniki z dziedziny algorytmów aproksymacyjnych. Dwie prace dotyczą poddziedziny optymalizacji stochastycznej, zaś wyniki ostatniej pracy leżą w przecięciu teorii algorytmów aproksymacyjnych i złożoności parametryzowanej. Przedstawione wyniki zawierają m.in. analizę algorytmów dla problemów pokryciowych w obliczu niepewności danych. W tym modelu rozważamy problemy takie jak np. Set Cover, przy założeniu, że cześć danych wejściowych jest nieznana z góry, zaś algorytm ma dostęp do rozkładu prawdopodobieństwa opisującego dane. Celem jest zbudowanie takiej struktury danych, która pozwoli odtworzyć rozwiązanie, kiedy całość danych zostanie ujawniona. Innym zagadnieniem jest konstrukcja mechanizmów i aukcji, w których decyzję odnośnie każdego klienta/przedmiotu należy podjąć zanim poznamy stan pozostałych. Poszukujemy strategii maksymalizującej oczekiwany zysk mechanizmu w oparciu o rozkład prawdopodobieństwa modelujący stan klientów/przedmiotów. W ostatniej części skupiam się na problemach grafowych, w których celem jest usunięcie możliwie małego podzbioru wierzchołków, tak aby graf należał do zadanej klasy. W prezentowanej pracy udało się osiągnąć znaczącą poprawę współczynników aproksymacji lub czasu działania algorytmów dla szeregu problemów tego typu.
dc.affiliation.departmentWydział Matematyki, Informatyki i Mechaniki
dc.contributor.authorWłodarczyk, Michał
dc.date.accessioned2019-07-03T12:44:49Z
dc.date.available2019-07-03T12:44:49Z
dc.date.defence2019-07-02
dc.date.issued2019-07-03
dc.description.additionalLink archiwalny https://depotuw.ceon.pl/handle/item/3435
dc.description.promoterCygan, Marek
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/3435
dc.language.isoen
dc.rightsCC-BY
dc.rightsCC-BY
dc.rights.uriCC-BY
dc.subject.enparameterized complexity
dc.subject.enstochastic optimization
dc.subject.enapproximation algorithms
dc.subject.plzłożoność parametryzowana
dc.subject.ploptymalizacja stochastyczna
dc.subject.plalgorytmy aproksymacyjne
dc.titleApproximation algorithms: new results for stochastic and parameterized problems
dc.title.alternativeAlgorytmy aproksymacyjne: nowe wyniki dla problemów stochastycznych i parametryzowanych
dc.typeDoctoralThesis
dspace.entity.typePublication