TY - JOUR A1 - Ghodselahi, Abdolhamid A1 - Kuhn, Fabian T1 - Toward Online Mobile Facility Location on General Metrics JF - Theory of Computing Systems N2 - We introduce an online variant of mobile facility location (MFL) (introduced by Demaine et al. (SODA 258–267 2007)). We call this new problem online mobile facility location (OMFL). In the OMFL problem, initially, we are given a set of k mobile facilities with their starting locations. One by one, requests are added. After each request arrives, one can make some changes to the facility locations before the subsequent request arrives. Each request is always assigned to the nearest facility. The cost of this assignment is the distance from the request to the facility. The objective is to minimize the total cost, which consists of the relocation cost of facilities and the distance cost of requests to their nearest facilities. We provide a lower bound for the OMFL problem that even holds on uniform metrics. A natural approach to solve the OMFL problem for general metric spaces is to utilize hierarchically well-separated trees (HSTs) and directly solve the OMFL problem on HSTs. In this paper, we provide the first step in this direction by solving a generalized variant of the OMFL problem on uniform metrics that we call G-OMFL. We devise a simple deterministic online algorithm and provide a tight analysis for the algorithm. The second step remains an open question. Inspired by the k-server problem, we introduce a new variant of the OMFL problem that focuses solely on minimizing movement cost. We refer to this variant as M-OMFL. Additionally, we provide a lower bound for M-OMFL that is applicable even on uniform metrics. KW - Mobile resources KW - Online requests KW - Competitive analysis KW - General cost function KW - Movement minimization Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2024022609363705445898 VL - 67 IS - 6 SP - 1268 EP - 1306 PB - Springer Nature CY - Berlin ER -