Efficient approximation algorithms for multi-antennae largest weight data retrieval

Abstract

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 δ -antennae largest weight data retrieval (δ ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using δ antennae in a given time interval. In this paper, we first give a linear programming (LP) relaxation for δ 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−1e for the δ -antennae γ -separated largest weight data retrieval (δ A γ LWDR) problem, a weaker version of δ ALWDR where each block of up to γ 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 δ A γ LWDR is NP− complete even for the simple case of γ=2 , m=3 , and equal-weight data items each appearing up to 3 times. Our algorithm runs in time O(2γm7T3.5L) , 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 α approximation solution to δ A γ LWDR implies a ratio α−ϵ approximation solution to δ ALWDR for any fixed ϵ>0 , we immediately have an approximation algorithm of ratio 1−1e−ϵ for δ ALWDR. Our algorithm has the same approximation ratio as the known result in [15] which holds only for δ=1 , with a significantly lower time complexity of O(21ϵ1ϵm7T3.5L) (improved from O(ϵ3.5m3.5ϵT3.5L) of [15] ). As a by-product, we also give a fixed-parameter tractable (fpt-)algorithm of time complexity O(2Bm7T3.5L) for δ ALWDR, where B is the number of time slots that contain data items with multiple occurrences.