Recent approaches to resource allocation in web monitoring target optimal performance under restricted capacity constraints [1], [2]. The resource allocation problem is generally modelled as a knapsack problem with known deterministic properties. However, for practical purposes the web must often be treated as stochastic and unknown. Unfortunately, estimating unknown knapsack properties (e.g., based on an estimation phase [1], [2]) delays finding an optimal or near-optimal solution. Dynamic environments aggravate this problem further when the optimal solution changes with time. In this paper, we present a novel solution for the nonlinear fractional knapsack problem with a separable and concave criterion function [3]. To render the problem realistic, we consider the criterion function to be stochastic with an unknown distribution. At every time instant, our scheme utilizes a series of informed guesses to move, in an online manner, from a "current" solution, towards the optimal solution. At the heart of our scheme, a game of deterministic learning automata performs a controlled random walk on a discretized solution space. Comprehensive experimental results demonstrate that the discretization resolution determines the precision of our scheme. In order to yield a required precision, the current resource allocation solution is consistently improved, until a near-optimal solution is found. Furthermore, our proposed scheme quickly adapts to periodically switching environments. Thus, we believe that our scheme is qualitatively superior to the class of estimation-based schemes.

Additional Metadata
Keywords Learning automata, Nonlinear knapsack problems, Resource allocation, Stochastic optimization
Persistent URL dx.doi.org/10.1109/ICCIS.2006.252228
Conference 2006 IEEE Conference on Cybernetics and Intelligent Systems
Citation
Granmo, O.-C. (Ole-Christoffer), Oommen, J, Myrer, S.A. (Svein A.), & Olsen, M.G. (Morten G.). (2006). Determining optimal polling frequency using a learning automata-based solution to the fractional knapsack problem. In 2006 IEEE Conference on Cybernetics and Intelligent Systems. doi:10.1109/ICCIS.2006.252228