Provably optimal dynamic programming

W 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.

In 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.