Mnich, MatthiasMatthiasMnich12032526410000-0002-4721-5354Kaul, MatthiasMatthiasKaul2025-11-242025-11-242025Technische Universität Hamburg (2025)https://hdl.handle.net/11420/58963We study parameterized approximation algorithms for optimization problems in graphs, specifically for Multi-Depot TSP (MDTSP) and Sparsest Cut. For MDTSP with d depots we are able to give for every ε > 0 a (1.5 + ε)-approximation algorithm running in time (1/ε)^O(d log d) · n^O(1), where previously only a 2-approximation in polynomial timeand a 1.5-approximation in XP time were known. We extend this line to also consider the case where all subtours are supposed to have similar size and give the first constant-factor all-norm approximation algorithm for Tree and Cycle Cover problems. For Sparsest Cut we continue and unify a line of research initiated by Chlamtáč, Krauthgamer, and Raghavendra(APPROX 2010) to give the first constant-factor approximation in time almost single-exponential in the tree-width of the capacity graph.Wir betrachten parameterisierte Approximationsalgorithmen f¨ur Optimierungsprobleme auf Graphen mit einem Fokus auf Multi-Depot TSP (MDTSP) und Sparsest Cut. F¨ur MDTSP mit d Depots geben wir f¨ur jedes ε > 0 einen (1.5+ε)-Approximationsalgorithmus mit Laufzeit (1/ε)^O(d log d) · n^O(1) an, wobei zuvor nur eine 2-Approximationsalgorithms mit polynomieller Laufzeit und ein 1.5-Approximationsalgorithms mit XP Laufzeit bekannt waren. Wir erweitern dies und betrachten auch den Fall, dass alle Subtouren ¨ahnliche L¨ange haben; Hier k¨onnen wir den ersten konstanten Approximationsalgorithmus bzgl. aller ℓp-Normen gleichzeitig angeben. F¨ur Sparsest Cut f¨uhren wir eine Forschungsrichtung von Chlamtáč, Krauthgamer, and Raghavendra (APPROX 2010) fort und geben den ersten Algorithmus der in fast einfachexponentieller Zeit in der Baumweite des Kapazit¨atsgraphen eine konstante Approximation berechnet.enhttps://creativecommons.org/licenses/by/4.0/Computer Science, Information and General Works::004: Computer SciencesNatural Sciences and Mathematics::519: Applied Mathematics, ProbabilitiesDoctoral Thesishttps://doi.org/10.15480/882.1620610.15480/882.16206Shachnai, HadasHadasShachnaiSpoerhase, JoachimJoachimSpoerhaseOther