2 results
Now showing1 - 2 of 2
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Parameterized approximation algorithms for optimization problems on graphs(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.Publicationtype: Doctoral Thesis57 63 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Exact and approximation algorithms for many-visits travelling salesperson problems(2022); The Many-Visits Path TSP is a natural generalisation of the Travelling Salesman Path Problem. We are given a set of cities, with pairwise distances between the cities, and in addition a visit requirement for each city. The aim is to find a minimum-cost walk between two specified end-vertices, that visits each city exactly as many times, as its requirement. In this thesis, we first provide an exact algorithm for the problem, that calculates an optimal solution in time exponential but space polynomial in the size of the input. The time and space complexities are asymptotically best possible. Moreover, we provide an efficient 1.5-approximation in case of metric distance costs, and constant-factor approximations for several variants of the problem with multiple agents.Publicationtype: Doctoral Thesis412 986