Competitive Analysis of Online Facility Assignment for General Layout of Servers on a Line
share
In the online facility assignment on a line OFAL(S,c) with a set S of k servers and a capacity c:S→ℕ, each server s∈ 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∈ 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α(S)+1)-competitive, where α(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, α(S) ranges from constant (independent of k) to k-1. Among all of known algorithms for OFAL(S,c), this upper bound on the competitive ratio is the best when α(S) is small. We also show that the competitive ratio of any MPFS (Most Preferred Free Servers) algorithm is at least 2α(S)+1. For OFAL(S,c), recall that MPFS is a class of algorithms whose competitive ratio does not depend on a capacity c and it includes the natural greedy algorithm and PTCP, etc. Thus, this implies that PTCP is the best for OFAL(S,c) in the class MPFS.
READ FULL TEXT