报告题目：Efficient Approximation Algorithms for Multi-Antennae Largest Weight Data Retrieval

报告人：计算科学与技术系郭龙坤

时间：2016.9.28(星期三) 16:00

地点：数计学院4号楼225

Abstract：In mobile networks, wireless data broadcast is a powerful approach for disseminating a large number of data copies to a great number of clients. The multi-antennae largest weight data retrieval problem, is to schedule downloading a specified subset of data items via multiple antennae in a given time interval, such that the weight of the downloaded items is maximized. We propose an linear programming (LP) formula for the relaxation of the problem, and show it is polynomial solvable when every data item appears at most once. On the other hand, we also shown when there exist data items with multiple occurrences, the integrality gap of this LP formula is 2 . As our main work, we designed an improved approximation algorithm with a factor 0.63.