K.I.-J. Ho, J. Wu, and J. Sum
Auction, E-Commerce, knapsack problems
This paper presents an approximated solution for an unbounded knapsack problem where the sizes of objects are discrete values: max zn(M) = 1 n ni =1 pixi s.t. ni =1 cixi ≤ β0n xi ∈ {0, 1} ∀i = 1, . . . , n where pis are the profits that are uniformly distributed random variables in [0,1]. The sizes cis are discrete random variables which are distributed uniformly in {1/M, 2/M, . . . , (M − 1)/M, 1}. zn(M) is the total profit to be maximized. Assuming that M is large, it is found that the optimal profit zn(M) is approximately equal to 2 β0/3(1 − 0.3062( √ β0M)−1). An example from auction is used to explain and illustrate the use of the derived solution in estimating the profit.
Important Links:
Go Back
