Logo des Repositoriums

Auflistung nach Autor:in "Tarnawski, Jakub"

1 - 2 von 2
  • Konferenzbeitrag
    Neue Graphen-Algorithmen mittels polyedrischer Methoden
    (Ausgezeichnete Informatikdissertationen 2019, 2020) Tarnawski, Jakub
    In dieser Arbeit werden neue Algorithmen für zwei grundlegende Graphenprobleme vorgestellt. Mit Hilfe von linearen Programmen – darunter auch Programme exponentieller Größe – werden Struktureigenschaften ermittelt die vomAlgorithmus verwendet werden. Etwas überraschend können ähnliche polyedrische Methoden in beiden Graphenproblemen angewendet werden. Der erste Teil der Dissertation widmet sich dem asymmetrischen Handlungsreisendenproblem (Asymmetric Traveling Salesman Problem – ATSP), einem Benchmark-Problem der kombinatorischen Optimierung. Bei diesem Problem geht es darum, die kürzeste Tour für einen erichteten und kantengewichteten Graphen zu finden, die alle Knoten besucht. Seit langem galt es als offen, ob es einen Approximationsalgorithmus für dieses Problem mit einer konstanten Güte gibt. Ein Ergebnis dieser Arbeit ist ein solcher Algorithmus. Der zweite Teil der Dissertation widmet sich dem perfekten Matching-Problem. Zudem wurde in den Achtzigerjahren gezeigt, dass es effiziente parallele Algorithmen für das Matching-Problem gibt, sofern die Verwendung von Zufälligkeit zulässig ist. Allerdings ist es noch offen ob das Matching-Problem in der Komplexitätsklasse NC liegt, also ob Zufälligkeit notwending ist. Diese Arbeit zeigt, dass das Matching-Problem in quasi-NC liegt.
  • Zeitschriftenartikel
    New graph algorithms via polyhedral techniques
    (it - Information Technology: Vol. 63, No. 3, 2021) Tarnawski, Jakub
    This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. The first part of the dissertation addresses a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A ρ -approximation algorithm for ATSP is one that runs in polynomial time and always produces a tour at most ρ times longer than the shortest tour. Finding such an algorithm with constant ρ had been a long-standing open problem. Here we give such an algorithm. The second part of the dissertation addresses the perfect matching problem. We have known since the 1980s that it has efficient parallel algorithms if the use of randomness is allowed. However, we do not know if randomness is necessary – that is, whether the matching problem is in the class NC . We show that it is in the class quasi-NC . That is, we give a deterministic parallel algorithm that runs in poly-logarithmic time on quasi-polynomially many processors.