The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study a variant where each demand request is a pair (x,w) where x is the standard location of the demand while w is the corresponding weight of the request. The cost of servicing request (x,w) at facility F is w⋅d(x,F). For this variant, given n requests, we present an online algorithm attaining a competitive ratio of O(log n) in the secretarial model for the weighted requests and show that it is optimal.
This is joint work with Prof. Rahul Vaze.
