Technical Report No. 283 - Abstract

Abdolhamid Ghodselahi, Fabian Kuhn
Optimally Serving Concurrent Requests on Hierarchically Well-Separated Trees

We consider the traveling salesman problem (TSP) with k?1 salespeople (k-TSP) on a hierarchically well-separated tree (HST). We show that the k-TSP can be optimally solved on HSTs. Based on this result, we show that the online service with delay (OSD) problem and the distributed queuing problem and even their generalized versions where there are k?1 servers are optimally solved on HSTs if the requests arrive at the same time.