Revisit the Online Facility Location Problem with Uniform Facility Cost

In the classical facility location problem, all information about potential facilities and clients is provided initially. However, obtaining complete information about all clients is challenging. When client information is provided incrementally, this gives rise to the online facility location problem. Both the online facility location problem with general facility costs and the one with uniform facility cost have attracted the attention of researchers. In the existing literature, the online facility location problem with uniform facility cost typically assumes that facilities can be located anywhere within the metric space. However, in practical scenarios where communication networks constructed by the facilities are graph-based, facility locations are limited to specific points on the network, this means that potential facility locations are discrete. In this work, we revisit the online facility location problem with uniform facility cost, focusing on scenarios where facilities can only be placed at discrete locations, known as the potential facility set. Considering clients arriving in a random order, we propose a 9.9-competitive online algorithm for the uniform facility cost case.