论文标题
设施位置的在线学习
Online Learning of Facility Locations
论文作者
论文摘要
在本文中，我们对设施位置问题的在线学习版本进行了严格的理论研究，该版本是由现实世界应用中新兴的问题引起的。在我们的公式中，我们将获得一组站点和在线用户请求的顺序。在每个试验中，学习者选择一个站点的子集，然后为每个选定站点的成本征收成本，而额外的成本是用户与所选子集中最近站点的连接的价格。该问题可以通过应用众所周知的树篱算法解决。但是，这将需要给定站点数量的时间和空间指数，这激发了我们针对此问题的新型准线性时间算法的设计，并具有良好的理论保证其性能。
In this paper, we provide a rigorous theoretical investigation of an online learning version of the Facility Location problem which is motivated by emerging problems in real-world applications. In our formulation, we are given a set of sites and an online sequence of user requests. At each trial, the learner selects a subset of sites and then incurs a cost for each selected site and an additional cost which is the price of the user's connection to the nearest site in the selected subset. The problem may be solved by an application of the well-known Hedge algorithm. This would, however, require time and space exponential in the number of the given sites, which motivates our design of a novel quasi-linear time algorithm for this problem, with good theoretical guarantees on its performance.
