On Unbounded Zero-One Knapsack With Discrete-Sized Objects
Authors:
- 1 January 2009
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computers and Applications
- Vol. 31 (2) , 84-89
Abstract
This paper presents an approximated solution for an unbounded knapsack problem where the sizes of objectsare discrete values: 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 An example from auction is used to explain and illustrate the use of the derived solution in estimating the profit.
Keywords
This publication has 6 references indexed in Scilit:
- ON PROFIT DENSITY BASED GREEDY ALGORITHM FOR A RESOURCE ALLOCATION PROBLEM IN WEB SERVICESInternational Journal of Computers and Applications, 2007
- Combinatorial auctions with decreasing marginal utilities2001
- Average-Case Analysis of Off-Line and On-Line Knapsack ProblemsJournal of Algorithms, 1998
- The Dynamic and Stochastic Knapsack ProblemOperations Research, 1998
- Stochastic on-line knapsack problemsMathematical Programming, 1995
- Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problemsOperations Research Letters, 1993