Optimality of Dual Methods for Discrete Multiuser Multicarrier Resource Allocation Problems

Authors

S. Görtzen, A. Schmeink,

Abstract

        Dual methods based on Lagrangian relaxation are the state of the art to solve multiuser multicarrier resource allocation problems. This applies to concave utility functions as well as to practical systems employing adaptive modulation, in which users' data rates can be described by step functions. We show that this discrete resource allocation problem can be formulated as an integer linear program belonging to the class of multiple-choice knapsack problems. As a knapsack problem with additional constraints, this problem is NP-hard, but facilitates approximation algorithms based on Lagrangian relaxation. We show that these dual methods can be described as rounding methods. As an immediate result, we conclude that prior claims of optimality, based on a vanishing duality gap, are insufficient. To answer the question of optimality of dual methods for discrete multicarrier resource allocation problems, we present bounds on the absolute integrality gap for three exemplary downlink resource allocation problems with different objectives when employing rounding methods. The obtained bounds are asymptotically optimal in the sense that the relative performance loss vanishes as the number of subcarriers tends to infinity. The exemplary problems considered in this work are sum rate maximization, sum power minimization and max-min fairness.

keywords={adaptive modulation;approximation theory;computational complexity;integer programming;knapsack problems;minimax techniques;multiuser channels;resource allocation;Lagrangian relaxation;NP-hard problem;absolute integrality gap;adaptive modulation;approximation algorithms;concave utility functions;discrete resource allocation problems;dual methods;exemplary downlink resource allocation problems;integer linear program;max-min fairness;multiple-choice knapsack problems;multiuser multicarrier resource allocation problems;optimality;sum power minimization;sum rate maximization;vanishing duality gap;Approximation algorithms;Linear programming;Minimization;Modulation;Optimization;Resource management;Wireless communication;Resource allocation;adaptive modulation;combinatorial optimization;duality theory;orthogonal frequency division multiple access (OFDMA)}
ISSN={1536-1276}

BibTEX Reference Entry 

@article{GoSc12,
	author = {Simon G{\"o}rtzen and Anke Schmeink},
	title = "Optimality of Dual Methods for Discrete Multiuser Multicarrier Resource Allocation Problems",
	pages = "3810-3817",
	journal = "{IEEE} Transactions on Wireless Communications",
	volume = "11",
	number = "10",
	doi = 10.1109/TWC.2012.091812.120513,
	month = Oct,
	year = 2012,
	hsb = hsb999910272994,
	}

Downloads

 Download paper  Download bibtex-file

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights there in are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.