Online Facility Assignment for General Layout of Servers on a Line

In the online facility assignment on a line \(\textrm{OFAL}(S,c)\) with a set S of k servers and a capacity \(c:S\rightarrow \mathbb {N}\) , each server \(s\in S\) with a capacity c(s) is placed on a line, and a request arrives on a line one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. An algorithm can match up to c(s) requests to a server \(s\in S\) . In this paper, we propose a new online algorithm PTCP (Policy Transition at Critical Point) for OFAL(S, c) and show that PTCP is \((2\alpha (S)+1)\) -competitive, where \(\alpha (S)\) is informally the ratio of the diameter of S to the maximum distance between two adjacent servers in S. Depending on the layout of servers, \(\alpha (S)\) ranges from O(1) to O(k). Among all of known algorithms for OFAL(S, c), this upper bound on the competitive ratio is the best when \(\alpha (S)\) is small. We also show that the competitive ratio of any MPFS (Most Preferred Free Servers) algorithm [6] is at least \(2\alpha (S)+1\) , where MPFS is a class of algorithms whose competitive ratio does not depend on a capacity c. Recall that the class MPFS includes the natural greedy algorithm and PTCP, etc. Thus, this implies that PTCP is the best for OFAL(S, c) in the class MPFS.