.png){kind=icon}
.png){kind=icon}
Return
Efficient Approximation Algorithms for Multi-Antennae Largest Weight Data Retrieval
.png){kind=icon}
OA
AI
DOI：10.1109/TMC.2017.2696009.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In a mobile network, wireless data broadcast over m channels (frequencies) is a powerful means for distributed dissemination of data to clients who access the channels through multi-antennae equipped on their mobile devices. The delta-antennae largest weight data retrieval (delta ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using delta antennae in a given time interval. In this paper, we first give a linear programming (LP) relaxation for delta ALWDR and show that it is polynomial-time solvable when every data item appears at most once. We also show that when there exist data items with multiple occurrences, the integrality gap of this LP formula is 2. We then present an approximation algorithm of ratio 1 - 1/e for the delta-antennae gamma-separated largest weight data retrieval (delta A gamma LWDR) problem, a weaker version of delta ALWDR where each block of up to gamma data (time) slots is separated by a vacant slot on all channels, applying the techniques called collectively randomized LP rounding and layered DAG construction. We show that delta A gamma LWDR is NP-complete even for the simple case of gamma = 2, m = 3, and equal-weight data items each appearing up to 3 times. Our algorithm runs in time O(2(gamma)m(7)T(3.5)L), where T is the number of time slots, and L is the maximum length of the input. Then, from the simple observation that a ratio alpha approximation solution to delta A gamma LWDR implies a ratio alpha - is an element of approximation solution to delta ALWDR for any fixed is an element of > 0, we immediately have an approximation algorithm of ratio 1 - 1/e - is an element of for delta ALWDR. Our algorithm has the same approximation ratio as the known result in [15] which holds only for delta = 1, with a significantly lower time complexity of O(2(1/is an element of)1/is an element of m(7)T(3.5)L) (improved from O(is an element of(3.5) m(3.5/)is an element of(TL)-L-3.5) . As a by-product, we also give a fixed-parameter tractable (fpt-) algorithm of time complexity O(2(B)m(7)T(3.5)L) for delta ALWDR, where B is the number of time slots that contain data items with multiple occurrences.
Keywords:
Distributed data dissemination
multi-antennae data retrieval
scheduling
approximation algorithm
linear programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
9.2
Papers:
5.6K
Citations:
1.8W