Logarithmic inapproximability of the radio broadcast problem

被引：27

作者：

Elkin, M

Kortsarz, G ^{[1
]}

机构：

[1] Rutgers State Univ, Comp Sci Dept, Camden, NJ 08102 USA

[2] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2004年 / 52卷 / 01期

关键词：

D O I：

10.1016/j.jalgor.2003.11.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that the radio broadcast problem is Omega(log n)-inapproximable unless NP subset of or equal to BPTIME (n(O(log log n))). Thisis the first result on the hardness of approximation of this problem. Our reduction is based on the reduction from the Label-Cover problem to the Set Cover problem due to Lund and Yannakakis [J. Assoc. Comput. Mach. 41 (5) (1994) 960-981], and uses some new ideas. (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：8 / 25

页数：18

共 20 条

[1] SINGLE ROUND SIMULATION ON RADIO NETWORKS [J].