Donald Bren School of Information and Computer Sciences

We analyze the expected difference between the solutions to the integer and linear versions of the 0-1 Knapsack Problem. This difference is of interest since it may help understand the efficiency of a fast backtracking algorithm for the integer 0-1 Knapsack Problem. We show that, under a fairly reasonable input distribution, the expected difference is 0(log^2 n/n) and Ω(1/n).