On profit density based greedy algorithm for a resource allocation problem in web services

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)155-162
Journal / PublicationInternational Journal of Computers and Applications
Volume29
Issue number2
Publication statusPublished - 2007

Abstract

Allocating limited computational resources to different clients is always a challenging problem to a web service provider (WSP). Profit density based greedy knapsack algorithm is one simple approach that can ensure near-optimal profit. However, profit gain is sometimes not the only factor concerned in making important management decisions. Other factors, such as the number of clients that a WSP can serve and the number of un-used resources that remain, are also important. By assuming that (a) the pricing curves of the buyer are all identical and their marginal utility (i.e., ΔPrice/ΔSize) is decreasing, (b) the resource is divisible, (c) the resource quantity each client requests follows uniform distribution U[0, 1] and (d) the available resource is constrained by k̄; equations for the expected number of clients who can get the resource, denoted by (6), and the expected quantity of resource being allocated, denoted by 〈s〉, are derived analytically. By observing the numerical plots of (b) and (s) against the number of clients n, it is found that (b) ≈ n for n ≤ 2k̄ and (b) ≈ (-1 + √1 + 8nk̄)/2 for n ≥ 2k̄. Comparing with another simple selling mechanism, we call it first-come-first-serve, it is found that resource allocation via greedy algorithm might not always be the best choice as far as the number of units being sold and the number of clients being served are concerned.

Research Area(s)

  • Knapsack problem, Order statistics, Profit density greedy algorithm, Sum of random variables, Uniform distribution