Online Facility Location with Deletions
Online Facility Location with Deletions
复制标题
DOI：
10.4230/lipics.esa.2018.21
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Marek Cygan;A. Czumaj;M. Mucha;P. Sankowski
中科院分区：
文献类型：
--
作者：
Marek Cygan;A. Czumaj;M. Mucha;P. Sankowski
在本文中，我们研究了在线设施位置问题的三个以前未经研究的变体，考虑到客户和设施不仅允许到达系统的内在情况，而且随时可以出发。我们从研究自然完全动态的在线非宣传模型的研究开始，可以添加和删除客户。客户到达时，必须将其分配到现有设施或在客户位置打开的新设施。但是，当一个也是开放设施之一的客户被删除时，我们的模型必须允许重新连接所有已连接到已删除设施的客户。在此模型中，我们提出了一个最佳O（log（n_ {act}） / log log（n_ {act}）） - 竞争算法，其中n_ {act}是输入序列末尾的活动端客户次数。接下来，我们将注意力转向电容设施的位置问题。我们首先注意到，如果不允许缺失，则可以实现O（log（n） / log（log n））的最佳竞争比，其中n是序列的长度。但是，当允许删除删除时，问题的电容版本比无竞争性的版本更具挑战性。我们表明，使用更复杂的算法方法，可以在完全动态模型中获得电容性设施位置问题的在线o（log n + log c log n） - 竞争算法，其中n是n是n是n的数量输入度量和C是任何开放设施的能力。
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment. We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing facility or to a new facility opened at the client's location. However, when a client who has been also one of the open facilities is to be removed, then our model has to allow to reconnect all clients that have been connected to that removed facility. In this model, we present an optimal O(log(n_{act}) / log log(n_{act}))-competitive algorithm, where n_{act} is the number of active clients at the end of the input sequence. Next, we turn our attention to the capacitated Facility Location problem. We first note that if no deletions are allowed, then one can achieve an optimal competitive ratio of O(log(n) / log(log n)), where n is the length of the sequence. However, when deletions are allowed, the capacitated version of the problem is significantly more challenging than the uncapacitated one. We show that still, using a more sophisticated algorithmic approach, one can obtain an online O(log N + log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where N is number of points in the input metric and c is the capacity of any open facility.