Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332692 | Journal of Computer and System Sciences | 2016 | 11 Pages |
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)+n2lgâ¡n)-time algorithm. For the unrestricted 1-median problem, we give an O(mn+n2lgâ¡lgâ¡n)-time algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Biing-Feng Wang, Jhih-Hong Ye, Pei-Jung Chen,