TUHH Open Research
Help
New user? Click here to register.Have you forgotten your password?
Communities & Collections
Publications
Research Data
People
Institutions
Projects
  1. Home
  2. Publications
  3. Publications
  4. Parameterized approximation algorithms for optimization problems on graphs

Parameterized approximation algorithms for optimization problems on graphs

Citation Link: https://doi.org/10.15480/882.16206
Publikationstyp
Doctoral Thesis
Date Issued
2025
Sprache
English
Author(s)
Kaul, Matthias
Advisor
Mnich, Matthias
Referee
Shachnai, Hadas
Spoerhase, Joachim
Title Granting Institution
Technische Universität Hamburg
Place of Title Granting Institution
Hamburg
Examination Date
2024-12-10
Institute
Algorithmen und Komplexität E-11
TORE-DOI
10.15480/882.16206
TORE-URI
https://hdl.handle.net/11420/58963
Citation
Technische Universität Hamburg (2025)
We 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.
DDC Class
004: Computer Sciences
519: Applied Mathematics, Probabilities
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Download
Name

Matthias_Kaul_Parameterized_Approximation_Algorithms.pdf

Size

1.88 MB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback