J. Sum, J. Wu, and C.-S. Leung
Knapsack problem, order statistics, profit density greedy algorithm,sum of random variables, uniform distribution
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 b , 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.
Important Links:
Go Back
