Online Facility Assignment

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 c(i) to facility f(j) before the next customer c(i+1) arrives. The cost of this assignment is the distance between ci and fj. The total number of customers is at most vertical bar F vertical bar 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 vertical bar F vertical bar and another one with competitive ratio vertical bar F vertical bar. Finally, we consider a variant in which the facilities are placed on the vertices of a graph and two algorithms in that setting.NSF [CCF-AF 1712119]12 month embargo; published online: 31 January 2018This item from the UA Faculty Publications collection is made available by the University of Arizona with support from the University of Arizona Libraries. If you have questions, please contact us at repository@u.library.arizona.edu