Online facility location with timed-requests and congestion
share
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 two variants of the online facility location problem; (1) timed requests and (2) congestion. Both of these variants are motivated by the applications to real life and the previously known results on online facility location cannot be directly adapted to analyse them. Timed requests : In this variant, each demand request is a pair (x,t) where the x is the standard location of the demand while t is the corresponding weight of the request. The cost of servicing request (x,t) at facility F is t· d(x,F') where F' is the set of facilities available at the time of request (x,t). For this variant, we present an online algorithm attaining a competitive ratio of 𝒪(log n) in the secretarial model for the timed requests and show that it is optimal. Congestion : The congestion variant considers the case when there is an additional congestion cost that grows with the number of requests served by each request. For this variant, when the congestion cost is a monomial, we show that there exists an algorithm attaining a constant competitive ratio. This constant is a function of the exponent of the monomial and the facility opening cost but independent of the number of requests.
READ FULL TEXT