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 ci to facility fj before the next customer ci+1 arrives. The cost of this assignment is the distance betwe...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-02, Vol.806, p.455-467
Main Authors: Ahmed, Abu Reyan, Saidur Rahman, Md, Kobourov, Stephen
Format: Article
Language:English
Subjects:
Greedy algorithms
Online facility assignment
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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|. We also consider a slightly more general situation where different facilities may have different capacities. Finally, we study a variant of the online facility assignment problem in which the facilities are placed on the vertices of a graph and present two algorithms for that setting.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.08.011