TY - JOUR
T1 - On profit density based greedy algorithm for a resource allocation problem in web services
AU - Sum, J.
AU - Wu, J.
AU - Leung, C. S.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Knapsack problem
KW - Order statistics
KW - Profit density greedy algorithm
KW - Sum of random variables
KW - Uniform distribution
UR - http://www.scopus.com/inward/record.url?scp=34250216980&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-34250216980&origin=recordpage
M3 - 21_Publication in refereed journal
VL - 29
SP - 155
EP - 162
JO - International Journal of Computers and Applications
JF - International Journal of Computers and Applications
SN - 1206-212X
IS - 2
ER -