Praca doktorska
Miniatura
Pliki
1000-DR-INF-189822.pdf1.34 MB
autoreferat-en (1).pdf321.32 KB
Licencja
FairUseKorzystanie z tego materiału możliwe jest zgodnie z właściwymi przepisami o dozwolonym użytku lub o innych wyjątkach przewidzianych w przepisach prawa. Korzystanie w szerszym zakresie wymaga uzyskania zgody uprawnionego.
 

Provably optimal dynamic programming

Uproszczony widok
dc.abstract.enIn this thesis we study an application of dynamic programming technique to graph problems and approximation algorithms. We improve upon state-of-the-art algorithms for All-Nodes Shortest Cycles, distance oracles, approximate algorithm for Partition, weak approximation for Subset Sum and others. We also present equivalence classes for certain problems, that admit algorithms based on dynamic programming. Namely: • (min, +)-convolution and knapsack problem, • (min, max)-convolution and strongly polynomial approximate (min, max) - convolution, • (min, max)-product and strongly polynomial approximate all-pairs shortest path.
dc.abstract.plW rozprawie przedstawiamy nowe techniki analizy algorytmów opartych na programowaniu dynamicznym. Używamy ich do rozwiązywania problemów na grafach i przyśpieszeniu wybranych algorytmów aproksymacyjnych. Zaproponowane przez nas metody pozwalają na usprawnienie obecnie znanych algorytmów dla znajdywania najkrótszych cykli, wyroczni odległości, problemów aproksymacyjnych związanych z problemem plecakowym i innych. W rozprawie proponujemy także klasy równoważności dla wybranych problemów, które mają efektywne algorytmy oparte na programowaniu dynamicznym. W szczególności: • (min, +)-konwolucji i problemu plecakowego, • (min, max)-konwolucji i silnie wielomianowej aproksymacji dla (min, +)-konwolucji, • (min, max)-produktu i silnie wielomianowej aproksymacji dla znajdywania najkrótszych ścieżek w grafie.
dc.affiliation.departmentWydział Matematyki, Informatyki i Mechaniki
dc.contributor.authorWęgrzycki, Karol
dc.date.accessioned2021-02-10T08:02:51Z
dc.date.available2021-02-10T08:02:51Z
dc.date.defence2021-02-18
dc.date.issued2021-02-10
dc.description.additionalLink archiwalny https://depotuw.ceon.pl/handle/item/3869
dc.description.promoterMucha, Marcin
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/3869
dc.language.isoen
dc.rightsFairUse
dc.subject.engraph algorithms
dc.subject.enAll-Pairs Shortest Path
dc.subject.enstrongly-polynomial algorithms
dc.subject.enfine-grained complexity
dc.subject.endynamic programming
dc.subject.enknapsack problem
dc.subject.entropical products
dc.subject.en+)-convolution
dc.subject.en(min
dc.subject.plalgorytmy grafowe
dc.subject.plproblem najkrótszych ścieżek
dc.subject.plalgorytmy silnie wielomianowe
dc.subject.pldokładna złożoność
dc.subject.plprogramowanie dynamiczne
dc.subject.plproblem plecakowy
dc.subject.plprodukty tropikalne
dc.subject.pl+)-konwolucja
dc.subject.pl(min
dc.titleProvably optimal dynamic programming
dc.title.alternativeProgramowanie dynamiczne z gwarancjami
dc.typeDoctoralThesis
dspace.entity.typePublication