1 results
Now showing1 - 1 of 1
- 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