Abstract
Facility Location Problems have always been studied with the assumption that the environment in the network is static and does not change over time. In practice, however, the environment is usually dynamic and we must consider the facility location in a global view. In this paper, we impose the following additional constraints on input facilities: the total number of facilities to be placed is not known in advance and a facility cannot be removed once it is placed. We solve this problem by presenting an algorithm to find a facility permutation such that any prefix of the permutation of facilities is near-optimal over any other facility subset.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K., Sharir, M.: Efficient Algorithms for Geometric Optimization. ACM Computing Surveys 30(4), 412–458 (1998)
Chudak, F.: Improved algorithms for uncapacitated facility location problem. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 180–194. Springer, Heidelberg (1998)
Current, J., Daskin, M., Schilling, D.: Discrete network location models. In: Drezner, Z., Hammacher, H.W. (eds.) Facility Location: Applications and Theory, pp. 81–118. Springer, Heidelberg (2002)
Current, J., Ratick, S., Revelle, C.: Dynamic facility location when the total number of facilities is uncertain: a decision analysis approach. European Journal of Operation Research 110(3), 597–609 (1998)
Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and k −median problems. In: Proc. FOCS 1999, pp. 378–388 (1999)
Chudak, F., Shmoys, D.B.: Improved approximation algorithms for capacitated facility location problem. In: Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (1999)
Fleischer, R., Golin, M.J., Yan, Z.: Online Maintenance of k −medians and k −covers on a line. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 102–113. Springer, Heidelberg (2004)
Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. In: Proc. of the 9th ACM-SIAM Symposium on Discrete Algorithms (1998): Also in Journal of Algorithms 31, 228–248 (1999)
Jain, K., Vazirani, V.: Primal-dual approximation algorithms for metric facility location and k −median problems. In: Proc. FOCS 1999 (1999)
Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 229–242. Springer, Heidelberg (2002)
Mettu, R.R., Plaxton, C.G.: The online median problem. In: Proc. FOCS 2000, pp. 339–348 (2000)
Plaxton, C.G.: Approximation algorithms for hierarchical location problems. In: Proc. STOC 2003, pp. 40–49 (2003)
Qin, Z., Xu, Y., Zhu, B.: On some optimization problems in obnoxious facility location. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol. 1858, pp. 320–329. Springer, Heidelberg (2000)
Shmoys, D.B.: Approximation algorithms for facility location problems. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 27–33. Springer, Heidelberg (2000)
Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proc. STOC 1997, pp. 265–274 (1997)
Sviridenko, M.: An 1.528-approximation algorithm for the metric uncapacitated facility location problem. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, p. 240. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dai, W., Xiao, P., Jiang, K. (2005). Facility Location in a Global View. In: Megiddo, N., Xu, Y., Zhu, B. (eds) Algorithmic Applications in Management. AAIM 2005. Lecture Notes in Computer Science, vol 3521. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496199_17
Download citation
DOI: https://doi.org/10.1007/11496199_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26224-4
Online ISBN: 978-3-540-32440-9
eBook Packages: Computer ScienceComputer Science (R0)