In the online and incremental variants of Facility Location, the demands arrive one-by-one and must be assigned to an open facility upon arrival, without any knowledge about future demands. In the online variant, the decisions of opening a facility at a particular location and of assigning a demand to some facility are irrevocable. In the incremental variant, the algorithm can also merge existing facilities (and the corresponding demand clusters) with each other, and only the decision of assigning some demands to the same facility is irrevocable. The goal is to maintain, either online or incrementally, a set of facilities and an assignment of the demands to them that minimize the total facility opening cost plus the assignment cost for all demands. In this survey, we discuss the previous work on online and incremental algorithms for Facility Location. In addition to the main results, namely that the competitive ratio for the online variant is Θ(log n/log log n), where n is the number of demands, and that the competitive ratio for the incremental variant is O(1), we discuss all known online and incremental Facility Location algorithms, sketch the intuition behind them and the main ideas of their competitive analysis, and discuss some applications.
展开▼
机译：在“设施位置”的在线和增量版本中，需求是一对一到达的，必须在到达时分配给开放设施，而无需任何关于未来需求的知识。在在线版本中，在特定位置开设设施并将需求分配给某些设施的决定是不可撤销的。在增量变体中，该算法还可以将现有设施（和相应的需求集群）彼此合并，并且只有将某些需求分配给同一设施的决定是不可撤销的。目标是在线或增量维护一组设备，并为其分配需求，以最大程度地减少总的设施开放成本加上所有需求的分配成本。在本次调查中，我们讨论了以前关于设施定位的在线算法和增量算法的工作。除了主要结果外，即在线变量的竞争比为Θ（log n / log log n），其中n为需求数量，增量变量的竞争比为O（1），我们讨论了所有已知的在线和增量设施定位算法，概述了它们背后的直觉以及竞争分析的主要思想，并讨论了一些应用程序。
展开▼
