@inproceedings{f6fd4052738b4fc8899204d500aada09,

title = "Online facility assignment",

abstract = "We consider the online facility assignment problem, with a set of facilities F of equal capacity l in metric space and customers arriving one by one in an online manner. We must assign customer ci to facility fj before the next customer ci+1 arrives. The cost of this assignment is the distance between ci and fj. The total number of customers is at most |F|l and each customer must be assigned to a facility. The objective is to minimize the sum of all assignment costs. We first consider the case where facilities are placed on a line so that the distance between adjacent facilities is the same and customers appear anywhere on the line. We describe a greedy algorithm with competitive ratio 4|F| and another one with competitive ratio |F|. Finally, we consider a variant in which the facilities are placed on the vertices of a graph and two algorithms in that setting.",

author = "Ahmed, {Abu Reyan} and Rahman, {Md Saidur} and Stephen Kobourov",

note = "Funding Information: Work on this project was funded in part by NSF grant CCF-AF 1712119. Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 12th International Conference and Workshop on Algorithms and Computation, WALCOM 2018 ; Conference date: 03-03-2018 Through 05-03-2018",

year = "2018",

doi = "10.1007/978-3-319-75172-6_14",

language = "English (US)",

isbn = "9783319751719",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "156--168",

editor = "Rahman, {M. Sohel} and Wing-Kin Sung and Ryuhei Uehara",

booktitle = "WALCOM",

}