Abstract
This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset Ai ⊆A of depots that i can potentially select from and use. When Ai =A for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an O(mnlg n)-time algorithm. For the restricted 1-median problem, we give an O(mnlg (|A|/m)+ n2 lg n)-time algorithm. For the unrestricted 1-median problem, we give an O(mn+ n2 lg lg n)-time algorithm.