OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Stochastic and fluid index policies for resource allocation problems

Larranaga, Maialen and Ayesta, Urtzi and Verloop, Maaike Stochastic and fluid index policies for resource allocation problems. (2015) In: IEEE Conference on Computer Communications (INFOCOM 2015), 26 April 2015 - 1 May 2015 (Hong Kong, Hong Kong).

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
503kB

Official URL: http://dx.doi.org/10.1109/INFOCOM.2015.7218498

Abstract

We develop a unifying framework to obtain efficient index policies for restless multi-armed bandit problems with birth-and-death state evolution. This is a broad class of stochastic resource allocation problems whose objective is to determine efficient policies to share resources among competing projects. In a seminal work, Whittle developed a methodology to derive well-performing (Whittle’s) index policies that are obtained by solving a relaxed version of the original problem. Our first main contribution is the derivation of a closed-form expression for Whittle’s index as a function of the steady-state probabilities. It can be efficiently calculated, however, it requires several technical conditions to be verified, and in addition, it does not provide qualitative insights into Whittle’s index. We therefore formulate a fluid version of the relaxed optimization problem and in our second main contribution we develop a fluid index policy. The latter does provide qualitative insights and is close to Whittle’s index. The applicability of our approach is illustrated by two important problems: optimal class selection and optimal load balancing. Allowing state-dependent capacities we can model important phenomena: e.g. power-aware server-farms and opportunistic scheduling in wireless systems. Numerical simulations show that Whittle’s index and our fluid index policy are both nearly optimal

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to IEEE editor. The definitive version is available at http://ieeexplore.ieee.org This papers appears in Proceedings of 2015 IEEE Conference on Computer Communications. Electronic ISBN: 978-1-4799-8381-0 The original PDF of the article can be found at: http://ieeexplore.ieee.org/document/7218498/?reload=true&arnumber=7218498 Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > IKERBASQUE (SPAIN)
Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (FRANCE)
Université de Toulouse > Institut National des Sciences Appliquées de Toulouse - INSA (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Euskal Herriko Unibertsitatea - EHU (SPAIN)
Laboratory name:
Statistics:download
Deposited By: IRIT IRIT
Deposited On:28 Sep 2016 14:09

Repository Staff Only: item control page