Online facility location with facility movements
Tóm tắt
Từ khóa
Tài liệu tham khảo
Anagnostopoulos A, Bent R, Upfal E, Van Hentenryck P (2004) A simple and deterministic competitive algorithm for online facility location. Inf Comput 194(2): 175–202
Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge
Christofides N, Beasley JE (1982) A tree search algorithm for the p-median problem. Eur J Oper Res 10(2): 196–204
Erlenkotter D (1978) A dual-based procedure for uncapacitated facility location. Oper Res 26(6): 992–1009
Fiat, A, Woeginger, GJ (eds) (1998) Online algorithms: the state of the art, LNCS 1442. Springer, Berlin
Fleischer R, Golin MJ, Yan Z (2004) Online maintenance of k-medians and k-covers on a line. Proc SWAT 2004 Springer LNCS 3111: 102–113
Fotakis D (2006) Incremental algorithms for facility location and k-median. Theor Comput Sci 361:275–313 (preliminary version appeared at the proccedings of ESA 04, LNCS 3221)
Fotakis D (2006) A primal-dual algorithm for online non-uniform facility location. J Discret Algorithms 5: 141–148
Fotakis D (2006) Memoryless facility location in one pass. In: Proceedings of STACS ’06, LNCS 3884, pp 608–620
Fotakis D (2008) On the competitive ratio for online facility location. Algorithmica 50(1):1–57 (preliminary version appeared at the proceedings of ICALP ’03, LNCS 2719)
Garfinkel RS, Neebe AW, Rao MR (1974) An algorithm for the M-median plant location problem. Transp Sci 8: 217–231
Hassin R, Tamir A (1991) Improved complexity bounds for location problems on the real line. Oper Res Lett 10: 395–402
Imreh Cs (2007) Competitive analysis. In: Iványi A (ed) Algorithms of Informatics, vol 1. mondAt, Budapest, pp 395–428
Shmoys D (2000) Approximation algorithms for facility location problems. In: Proceedings of 3rd international workshop of approximation algorithms for combinatorial optimization, Springer LNCS, vol 1913, pp 27–33