Competitive Analysis of Online Facility Open Problem

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.

Authors

• Binghan Wu University of Sydney
• Wei Bao University of Sydney
• Bing Zhou

Keywords

• Online algorithms
• Competitive analysis
• Facility location problem