论文标题
在线设施的位置，重量和拥堵
Online facility location with weights and congestion
论文作者
论文摘要
经典的在线设施位置问题涉及在线要求到达时，以在线方式找到最佳设施，并且需要打开设施以服务这些请求。在这项工作中，我们研究了在线设施位置问题的两个变体； （1）加权请求和（2）拥塞。这两种变体都是由于它们在现实生活中的应用而激发的，并且在线设施位置上先前已知的结果无法直接适应以分析它们。 加权请求：在此变体中，每个需求请求都是$（x，w）$，其中$ x $是需求的标准位置，而$ w $是请求的相应权重。在设施$ f $的服务请求$（x，w）$的费用为$ w \ cdot d（x，f）$。对于此变体，给定$ n $请求，我们提出了一种在线算法，该算法在秘书模型中以$ \ MATHCAL {O}（\ log n）$的竞争比为重量，并表明其最佳。 拥塞：充血变体考虑了额外的拥塞成本随着每个设施提供的要求数量而增长的案件。对于这种变体，当拥堵成本是单一的，我们表明存在一种达到持续竞争比率的算法。该常数是单一指数和设施开放成本的函数，但独立于请求数量。
The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study two variants of the online facility location problem; (1) weighted requests and (2) congestion. Both of these variants are motivated by their applications to real life scenarios and the previously known results on online facility location cannot be directly adapted to analyse them. Weighted requests: In this variant, each demand request is a pair $(x,w)$ where $x$ is the standard location of the demand while $w$ is the corresponding weight of the request. The cost of servicing request $(x,w)$ at facility $F$ is $w\cdot d(x,F)$. For this variant, given $n$ requests, we present an online algorithm attaining a competitive ratio of $\mathcal{O}(\log n)$ in the secretarial model for the weighted requests and show that it is optimal. Congestion: The congestion variant considers the case when there is an additional congestion cost that grows with the number of requests served by each facility. For this variant, when the congestion cost is a monomial, we show that there exists an algorithm attaining a constant competitive ratio. This constant is a function of the exponent of the monomial and the facility opening cost but independent of the number of requests.
