2023/08/11 by Tsubasa Harada, Harada, Tsubasa, Toshiya Itoh +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2308.05933
openalex publication_date 2023/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the online facility assignment on a line \rm 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.