Online algorithms for facility assignment problem

Abstract

Consider an online facility assignment problem where a set of facilities F of equal capacity l is situated on a metric space and customers arrive one by one in an online manner on that space. We assign a customer ci to a facility fj be- fore a new customer ci+1 arrives. The cost of this assignment is the distance between ci and fj . The objective of this problem is to minimize the sum of all assignment costs. In this thesis we first consider F is situated on a straight line having equal distance between adjacent facilities and customers appear anywhere on the same straight line. We propose Algorithm Greedy which is 4|F|-competitive. After introducing randomization in Algorithm Greedy, we show that it is 9 2 -competitive for a class of input sequences. We provide another method Algorithm Optimal-Fill which is |F|-competitive. We also study another greedy method named Algorithm Capacity-Sensitive-Greedy. Consider now instead of a straight line, F is situated on the vertices of a con- nected unweighted graph G and customers arrive one by one having positions on the vertices of G. We show Algorithm Greedy is 2|E(G)|-competitive and Algorithm Optimal-Fill is |E(G)||F|/r-competitive where r is the radius of G. We introduce service time parameter t in our modeling and show that no deterministic algorithm is competitive when t = 2. We also provide a sim- ulation of the algorithms and define a new parameter named experimental competitive ratio. We analyse the simulation data in terms of experimental competitive ratio.