Asymptotic Analysis on an Unbounded Zero-One Knapsack with Discrete-Sized Objects

摘要

The average profit gain, Equation (4), for the unbounded knapsack problem with fractional sized objects has been derived. An extended result for the case that object size is discrete has been obtained. It has been shown that the average discrete-sized profit gain can be expressed in term of β_0 and M as ((2β_0)/3)~(1/2)-0.3062((β_0)~(1/2)M)~(-1). An application of this result in multi-unit combinatorial auction has been presented. Without loss of generality, the case when p_i's are discrete random variables can also be derived using the same technique used in the paper.