论文标题
非现有设施位置几乎最佳的确定性在线算法
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
论文作者
论文摘要
在设施位置问题的在线非现量变体中，有一个给定的图表，该图由设施的集合（每个设施都有一定的开放成本），一组潜在客户的$ c $以及它们之间的加权连接。输入的在线部分是$ c $的一系列客户端，并且为了对任何请求的客户端响应，在线算法可能会打开一个额外的设施子集，并且必须将给定客户端连接到开放设施。 我们为此问题提供了一个在线，多项式的确定性算法，其竞争比为$ O（\ log | f | \ cdot（\ log | c | c | + \ log \ log \ log \ log \ log | f |））$。结果是最佳的日志因素。我们的算法改进了$ o（（（\ log | c | + \ log | f |）\ cdot（\ log | c | + \ log \ log \ log | f |））$ - 竞争性结构首先将设施位置的实例降低到设置覆盖范围，然后使用Alon Et eT eT eT eT and and and and and and Algorithm sot cover。 [Talg 2006]。在$ | f |的典型情况下，这是渐近的改进。 \ ll | c | $。 我们通过一种更直接的方法实现了这一目标：我们设计了一种算法，用于与集群设施的非现场设施位置问题分数放松。为了处理这种非覆盖LP的限制，我们结合了双拟合和乘法重量更新方法。通过维护创建的分数解决方案的某些其他单调性属性，我们可以在舍入例程中处理设施和连接之间的依赖关系。 我们的结果与Naor等人的算法结合在一起。 [FOCS 2011]产生了在线节点加权Steiner树问题的第一个确定性算法。最终的竞争比为$ O（\ log k \ cdot \ log^2 \ ell）$在$ \ ell $ nodes和$ k $ terminals上。
In the online non-metric variant of the facility location problem, there is a given graph consisting of a set $F$ of facilities (each with a certain opening cost), a set $C$ of potential clients, and weighted connections between them. The online part of the input is a sequence of clients from $C$, and in response to any requested client, an online algorithm may open an additional subset of facilities and must connect the given client to an open facility. We give an online, polynomial-time deterministic algorithm for this problem, with a competitive ratio of $O(\log |F| \cdot (\log |C| + \log \log |F|))$. The result is optimal up to loglog factors. Our algorithm improves over the $O((\log |C| + \log |F|) \cdot (\log |C| + \log \log |F|))$-competitive construction that first reduces the facility location instance to a set cover one and then later solves such instance using the deterministic algorithm by Alon et al. [TALG 2006]. This is an asymptotic improvement in a typical scenario where $|F| \ll |C|$. We achieve this by a more direct approach: we design an algorithm for a fractional relaxation of the non-metric facility location problem with clustered facilities. To handle the constraints of such non-covering LP, we combine the dual fitting and multiplicative weight updates approach. By maintaining certain additional monotonicity properties of the created fractional solution, we can handle the dependencies between facilities and connections in a rounding routine. Our result, combined with the algorithm by Naor et al. [FOCS 2011] yields the first deterministic algorithm for the online node-weighted Steiner tree problem. The resulting competitive ratio is $O(\log k \cdot \log^2 \ell)$ on graphs of $\ell$ nodes and $k$ terminals.
