Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
复制标题
DOI：
10.1145/950620.950621
复制
发表时间：
2002-07
期刊：
影响因子：
--
通讯作者：
K. Jain;Mohammad Mahdian;E. Markakis;A. Saberi;V. Vazirani
中科院分区：
文献类型：
--
作者：
K. Jain;Mohammad Mahdian;E. Markakis;A. Saberi;V. Vazirani
在这篇文章中，我们将形式化的对偶拟合的方法和因子揭示LP的想法。这种组合是用来设计和分析两个贪婪算法的度量无能力限制的设施选址问题。它们的近似因子分别为1.861和1.61，运行时间分别为O（mlog m）和O（n3），其中n是城市和设施之间的基本完全二部图中的顶点总数，m是边数。该算法被用来改善最近的几个变种的问题的结果。
In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(m log m) and O(n3), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.