K.I.-J. Ho, J. Wu, and J. Sum
[1] T.-C. Lai, Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems, Operations Research Letters, 14, 1993, 215–220. [2] G.S. Lueker, Average-case analysis of off-line and on-line knapsack problems, Journal of Algorithms, 29, 1998, 277–305. [3] A. Marchetti-Spaccamela & C. Vercellis, Stochastic on-line knapsack problems, Mathematical Programming, 68, 1995, 73–104. [4] D. Chakrabarty, Y. Zhou, & R. Lukose, Budget constrained bidding in keyword auctions and online knapsack problems, WWW2007, May 2007, 8–12. [5] A.J. Kleywegt & J.D. Papastavriou, The dynamic and stochastic knapsack problem, Operations Research, 46 (1), 1998, 17–35. [6] V. Krishna, Auction theory (New York: Academic Press, 2002). [7] E.S. Maskin & J.G. Riley, Optimal multi-unit auctions, The Economics of Missing Markets, Information, and Games, (New York: Oxford University Press, 1989). [8] B. Lehmann, D. Lehmann, & N. Nisan, Combinatorial auctions with decreasing marginal utilities, Proc. 3rd ACM Conf. on Electronic Commerce, Tampa, Florida, 2001, 18–28. [9] J. Sum, J. Wu, & C. Leung, On profit density based greedy algorithm for a resource allocation problem in web services, International Journal of Computers and Applications, 29(2), 2007. [10] J. Sum, K. Ho, & G. Young, Pricing web services, in Y.-C. Chung & J.E. Moreira (Eds.), Advances in grid & pervasive computing, (Berlin, Heidelberg: Springer LNCS No.3947, 2006), 147–156. Appendix: MATLAB Code for the example in Section 5MM = 20;R = zeros(MM,100);T = 500;n = 10000;b = 0.2;pmax = 100;k = bn1000;for repeat = 1:100,r = round(1000betarnd(15,5,n,1));p = pmax(1-exp(-r/T));[yr ir] = sort(p./r);ktmp = 0; t = 1; z = 0;while (ktmp < k)z = z + p(ir(t));ktmp = ktmp + r(ir(t));t = t + 1;end for mm = 1:MM,M = 5mm;rd = round(r/M)M;pd = pmax(1-exp(-rd/T));[yd id] = sort(pd./rd);ktmp = 0; t = 1; zd = 0;while (ktmp < k)zd = zd + pd(ir(t));ktmp = ktmp + rd(ir(t));t = t + 1;endR(mm,repeat) = zd/z;endend88
Important Links:
Go Back
