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 条

[1]

Anceaume Emmanuelle., 2006, PROC 26 INT C DISTRI, P22

[2]

Angluin D, 2010, LECT NOTES ARTIF INT, V6331, P104, DOI 10.1007/978-3-642-16108-7_12

[3]

[Anonymous], 2010, The Design of Approximation Algorithms, DOI DOI 10.1017/CBO9780511921735

[4]

[Anonymous], 2007, P ACM INT C DISTR EV

[5] STRUCTURE PRESERVING REDUCTIONS AMONG CONVEX-OPTIMIZATION PROBLEMS [J].

AUSIELLO, G ;

DATRI, A ;

PROTASI, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 21 (01) :136-153

[6] A LINEAR-TIME APPROXIMATION ALGORITHM FOR THE WEIGHTED VERTEX COVER PROBLEM [J].

BARYEHUDA, R ;

EVEN, S .

JOURNAL OF ALGORITHMS, 1981, 2 (02) :198-203

[7]

Carzaniga A, 2004, IEEE INFOCOM SER, P918

[8]

Chand R, 2005, LECT NOTES COMPUT SC, V3648, P1194

[9]

Chlebík M, 2003, LECT NOTES COMPUT SC, V2751, P27

[10]

Chockler G, 2007, PODC'07: PROCEEDINGS OF THE 26TH ANNUAL ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, P109

← 1 2 3 →