On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
作者： Jun Hosoda , Juraj Hromkovič , Taisuke Izumi , Hirotaka Ono , Monika Steinová
DOI: 10.1007/978-3-642-22993-0_35
关键词:
摘要: In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: Given set t topics, collection n users together with lists topics they are interested in, aim is connect these by minimum number edges such that every graph induced common topic connected. It known Min-TCO NP-hard and approximable within O(log t) polynomial time. In this paper, we further investigate some its special instances. We give various hardness results for instances where constant, also which an user bounded constant. Furthermore, close gap showing LOGAPX-completeness. present few polynomial-time algorithms very restricted Min-TCO.
springer.com
elsevier.com
springerlink.com参考文章(26)
Emin Gün Sirer, Venugopalan Ramasubramanian, Ryan Peterson, Corona: a high performance publish-subscribe system for the world wide web networked systems design and implementation. pp. 2- 2 ,(2006)
Juraj Hromkovič, Algorithmics for Hard Problems Springer-Verlag New York, Inc.. ,(2002) , 10.1007/978-3-662-04616-6
Madhu Sudan, Sanjeev Khanna, Nadia Creignou, Complexity classifications of Boolean constraint satisfaction problems ,(1987)
Daniel Sandler, Alan Mislove, Ansley Post, Peter Druschel, FeedTree: Sharing Web Micronews with Peer-to-Peer Event Notification Peer-to-Peer Systems IV. pp. 141- 151 ,(2005) , 10.1007/11558989_13
Miroslav Chlebík, Janka Chlebíková, Inapproximability Results for Bounded Variants of Optimization Problems Fundamentals of Computation Theory. pp. 27- 38 ,(2003) , 10.1007/978-3-540-45077-1_4
Hassan Masum, Review of Algorithmics for hard problems ACM SIGACT News. ,vol. 34, pp. 6- 8 ,(2003) , 10.1145/882116.882121
Dana Angluin, James Aspnes, Lev Reyzin, Inferring social networks from outbreaks algorithmic learning theory. pp. 104- 118 ,(2010) , 10.1007/978-3-642-16108-7_12
Eran Halperin, Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs SIAM Journal on Computing. ,vol. 31, pp. 1608- 1623 ,(2002) , 10.1137/S0097539700381097
G. Ausiello, A. D'Atri, M. Protasi, Structure preserving reductions among convex optimization problems Journal of Computer and System Sciences. ,vol. 21, pp. 136- 153 ,(1980) , 10.1016/0022-0000(80)90046-X
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev, A new multilayered PCP and the hardness of hypergraph vertex cover symposium on the theory of computing. pp. 595- 601 ,(2003) , 10.1145/780542.780629