On the approximability and hardness of minimum topic connected overlay and its special instances

被引：12

作者：

Hosoda, Jun ^{[3
]}

Hromkovic, Juraj ^{[1
]}

Izumi, Taisuke ^{[3
]}

Ono, Hirotaka ^{[2
]}

Steinova, Monika ^{[1
]}

Wada, Koichi ^{[3
]}

机构：

[1] Swiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland

[2] Kyushu Univ, Dept Econ Engn, Fukuoka 812, Japan

[3] Nagoya Inst Technol, Grad Sch Engn, Nagoya, Aichi, Japan

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 429卷

基金：

日本学术振兴会;

关键词：

Topic-connected overlay; Approximation algorithm; APX; Hardness; APPROXIMATION; OPTIMIZATION; ALGORITHMS;

D O I：

10.1016/j.tcs.2011.12.033

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: given a set oft topics and a collection of n 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. It is known that min-TCO is NP-hard and approximable within O(log t) in polynomial time. In this paper, we further investigate the problem and some of its special instances. We give various hardness results for instances where the number of topics in which a user is interested in is bounded by a constant, and also for the instances where the number of users interested in a common topic is a constant. For the latter case, we present a first constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：144 / 154

页数：11

共 24 条

[11]

Creignou N., 2001, SIGACT News, V32, P24, DOI 10.1145/568425.568432

[12]

Dinur I., 2003, STOC, P595

[13] Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs [J].

Halperin, E .

SIAM JOURNAL ON COMPUTING, 2002, 31 (05) :1608-1623

[14]

Hromkovic J., 2003, ALGORITHMICS HARD PR, P538

[15] Vertex cover might be hard to approximate to within 2-ε [J].

Khot, Subhash ;

Regev, Oded .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (03) :335-349

[16]

Khot Subhash, 2002, P 34 ANN ACM S THEOR, P767, DOI [DOI 10.1145/509907.510017, 10.1109/CCC.2002.1004334, DOI 10.1109/CCC.2002.1004334]

[17] The clustering matroid and the optimal clustering tree [J].

Korach, E ;

Stern, M .

MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :385-414

[18] The complete optimal stars-clustering-tree problem [J].

Korach, Ephraim ;

Stern, Michal .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (04) :444-450

[19] On efficient fixed-parameter algorithms for weighted vertex cover [J].

Niedermeier, R ;

Rossmanith, P .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 47 (02) :63-77

[20] Minimum Maximum Degree Publish-Subscribe Overlay Network Design [J].

Onus, Melih ;

Richa, Andrea W. .

IEEE INFOCOM 2009 - IEEE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-5, 2009, :882-890

← 1 2 3 →