On the hardness and approximation of minimum topic-connected overlay
On the hardness and approximation of minimum topic-connected overlay
复制标题
关于最小主题连接覆盖的硬度和近似
DOI：
10.1145/1993806.1993861
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Monika Steinová
中科院分区：
文献类型：
--
作者：
Monika Steinová
设计可扩展的覆盖网络来支持分散的基于主题的发布/订阅通信是当今一个非常重要的问题。我们在这里研究一种称为“最小主题连接覆盖”的设计问题的特殊实例。给定用户集合以及他们感兴趣的主题列表，目标是通过最少数量的边将这些用户连接到网络，以便连接对共同主题感兴趣的用户生成的每个图。我们还研究了对特定主题感兴趣的用户数量受常数 d > 2 限制的情况。众所周知，一般的主题连接覆盖是 Ω(log n) ，难以近似，但可以通过对数因子近似。对于我们的特殊实例，我们设计了对击球集问题的特殊实例的一对一简化。这使我们能够针对所讨论的特殊实例提出第一个常数近似算法、第一个核化和第一个非平凡的精确算法。
The design of a scalable overlay network to support decentralized topic-based publish/subscribe communication is nowadays a problem of a great importance. We investigate here special instances of one such design problem called Minimum Topic-Connected Overlay. Given a collection of users together with the lists of topics they are interested in, the aim is to connect these users to a network by a minimum number of edges such that every graph induced by users interested in a common topic is connected. We investigate instances where in addition the number of users interested in a particular topic is bounded by a constant d > 2. It is known that the general Topic-Connected Overlay is Ω(log n) hard to approximate and approximable by a logarithmic factor. For our special instances, we design a one-to-one reduction to special instances of the hitting set problem. This allows us to present the first constant approximation algorithm, the first kernelization and the first nontrivial exact algorithm for the special instances discussed.