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.
