The Two-Constraint Binary Knapsack Problem’s average case analysis for constraints with small, moderate and large coefficients

Szkatuła, Krzysztof

doi:10.2478/candc-2025-0007

Abstract

The paper addresses the Two-Constraint Binary Knapsack Problem. It is assumed that some of the problem coefficients are the realizations of mutually independent random variables. Asymptotic probabilistic properties of selected problem characteristics are investigated for special cases of Lagrange multipliers with small, moderate and mixed values.

References

Averbakh, I. (1994) Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms. Mathematical Programming, 65: 311–330.
Search in Google Scholar Back to article
Frieze, A. and Clarke, M. (1984) Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst case and probabilistic analysis. European Journal of Operational Research, 15: 100–109.
Search in Google Scholar Back to article
Garey, M. and Johnson, D. (1970) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
Search in Google Scholar Back to article
Lee, T.-E. and Oh, G.-T. (1997) The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem. European Journal of Operational Research, 103: 584–594.
Search in Google Scholar Back to article
Loéve, M. (1977) Probability Theory I. Springer Verlag, New York, Heidelberg, Berlin.
Search in Google Scholar Back to article
Mamer, J. and Schilling, K. (1990) On the growth of random knapsacks. Discrete Applied Mathematics, 28: 223–230.
Search in Google Scholar Back to article
Martello, S. and Toth, P. (1990) Knapsack Problems: Algorithms and Computer Implementations. Wiley & Sons.
Search in Google Scholar Back to article
Meanti, M., Kan, A. R., Stougie, L. and Vercellis, C. (1990) A probabilistic analysis of the multiknapsack value function. Mathematical Programming, 46: 237–247.
Search in Google Scholar Back to article
Nemhauser, G. and Wolsey, L. (1988) Integer and Combinatorial Optimization. John Wiley & Sons Inc., New York.
Search in Google Scholar Back to article
Schilling, K. (1990) The growth of m-constraint random knapsacks. European Journal of Operational Research, 46: 109–112.
Search in Google Scholar Back to article
Schilling, K. (1994) Random knapsacks with many constraints. Discrete Applied Mathematics, 48: 163–174.
Search in Google Scholar Back to article
Szkatu la, K. (1994) On the growth of multi-constraint random knapsacks with various right-hand sides of the constraints. European Journal of Operational Reserch, 73: 199–204.
Search in Google Scholar Back to article
Szkatu la, K. (1997) The growth of multi-constraint random knapsacks with large right-hand sides of the constraints. Operations Research Letters, 21: 25–30.
Search in Google Scholar Back to article
Szkatu la, K. (2021) When two-constraint binary knapsack problem is equivalent to classical knapsack problem? In: K. T. Atanassov, V. Atanassova, J. Kacprzyk, A. Ka luszko, M. Krawczak, J. W. Owsiński, S. S. Sotirov,
Search in Google Scholar Back to article
E. Sotirova, E. Szmidt, and S. Zadrożny, eds., Advances and New Developments in Fuzzy Logic and Technology, Cham, Springer International Publishing, 311–321.
Search in Google Scholar Back to article

The Two-Constraint Binary Knapsack Problem’s average case analysis for constraints with small, moderate and large coefficients

Abstract

Paradigm

My account