Abstract
In the Movement Repairmen (MR) problem we are given a metric space (V, d) along with a set R of k repairmen r 1, r 2, …, r k with their start depots s 1, s 2, …, s k ∈ V and speeds v 1, v 2, …, v k ≥ 0 respectively and a set C of m clients c 1, c 2, …, c m having start locations s′1, s′2, …, s′ m ∈ V and speeds v′1, v′2, …, v′ m ≥ 0 respectively. If t is the earliest time a client c j is collocated with any repairman (say, r i ) at a node u, we say that the client is served by r i at u and that its latency is t. The objective in the (Sum-MR) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients latencies. The motivation for this problem comes, for example, from Amazon Locker Delivery [Ama10] and USPS gopost [Ser10]. We give the first O(logn)-approximation algorithm for the Sum-MR problem. In order to solve Sum-MR we formulate an LP for the problem and bound its integrality gap. Our LP has exponentially many variables, therefore we need a separation oracle for the dual LP. This separation oracle is an instance of Neighborhood Prize Collecting Steiner Tree (NPCST) problem in which we want to find a tree with weight at most L collecting the maximum profit from the clients by visiting at least one node from their neighborhoods. The NPCST problem, even with the possibility to violate both the tree weight and neighborhood radii, is still very hard to approximate. We deal with this difficulty by using LP with geometrically increasing segments of the time line, and by giving a tricriteria approximation for the problem. The rounding needs a relatively involved analysis. We give a constant approximation algorithm for Sum-MR in Euclidean Space where the speed of the clients differ by a constant factor. We also give a constant approximation for the makespan variant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amazon. Amazon locker delivery (2010), http://www.amazon.com/gp/help/customer/display.html?nodeId=200689010
Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: ACM Symposium on Theory of Computing, pp. 163–171 (1994)
Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Information and Computation 106, 234 (1993)
Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: IEEE Symposium on Foundations of Computer Science, pp. 36–45 (2003)
Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX and RANDOM 2004. LNCS, vol. 3122, pp. 72–83. Springer, Heidelberg (2004)
Chakrabarty, D., Swamy, C.: Facility location with client latencies: Linear programming based techniques for minimum latency problems. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 92–103. Springer, Heidelberg (2011)
Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairman problem. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 655–664 (2003)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences 69(3), 485–497 (2004)
Goemans, M., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. Mathematical Programming 82(1), 111–124 (1998)
Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 389–398 (2001)
Hajiaghayi, M.T., Khandekar, R., Reza Khani, M., Kortsarz, G.: Approximation algorithms for movement repairmen. arXiv:1306.3739 [cs.DS] (2013)
The United States Postal Service. gopost (2010), https://tools.usps.com/go/EPLActioninput
Sitters, R.: The minimum latency problem is NP-hard for weighted trees. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 230–239. Springer, Heidelberg (2002)
Swamy, C., Kumar, A.: Primal–dual algorithms for connected facility location problems. Algorithmica 40(4), 245–269 (2004)
Will, T.G., Adviser-West, D.B.: Extremal results and algorithms for degree sequences of graphs (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hajiaghayi, M., Khandekar, R., Khani, M.R., Kortsarz, G. (2013). Approximation Algorithms for Movement Repairmen. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2013 2013. Lecture Notes in Computer Science, vol 8096. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40328-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-40328-6_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40327-9
Online ISBN: 978-3-642-40328-6
eBook Packages: Computer ScienceComputer Science (R0)