Parameterized approximation algorithms for optimization problems on graphs

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/

Name

Matthias_Kaul_Parameterized_Approximation_Algorithms.pdf

Size

1.88 MB

Format

Adobe PDF

Options

Parameterized approximation algorithms for optimization problems on graphs