Competitive Analysis of Online Facility Open Problem

Binghan Wu (The University of Sydney), Wei Bao (The University of Sydney), Bing Zhou (The University of Sydney)

Abstract

We investigate an online cost minimization problem of serving requests in a tree of facilities, referred to as the Online Facility Open Problem (Online FOP). To address this problem, we propose the Anchor-Barrier Algorithm (ABA), a threshold-based algorithm applicable to any tree and any cost assignment, which can work in a distributed manner for scalability. We conduct the competitive analysis and show that ABA's achieves the optimal competitive ratio Height + 2, where Height is the height of the facility tree.