Radio aggregation scheduling
Radio aggregation scheduling
复制标题
无线聚合调度
DOI：
10.1016/j.tcs.2020.07.032
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Oh, Hoon
中科院分区：
文献类型：
--
作者：
Gandhi, Rajiv;Halldórsson, Magnús M.;Konrad, Christian;Kortsarz, Guy;Oh, Hoon
我们考虑无线电网络中的聚合问题：在给定图中找到生成树和边的无冲突调度，以最小化计算延迟。虽然存在大量关于此问题和相关问题的文献，但我们在图表中给出了第一个近似结果，这些结果不是由平面中的单位范围导出的。我们给出了一个多项式时间 O~(d n) 逼近算法，其中 d 是平均度，n 是图中的顶点数，并且表明问题是 Ω (n 1− ϵ)-hard（和 Ω ((d n) 1/2− ϵ)-hard），即使在二分图上也能进行近似，对于任何 ϵ> 0，使我们的算法本质上是最优的。我们还在区间图中获得了 O (log n) 近似值。
We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time O˜(d n)-approximation algorithm, where d is the average degree and n the number of vertices in the graph, and show that the problem is Ω (n 1− ϵ)-hard (and Ω ((d n) 1/2− ϵ)-hard) to approximate even on bipartite graphs, for any ϵ> 0, rendering our algorithm essentially optimal. We also obtain a O (log n)-approximation in interval graphs.