Ratios of optimal values of objective functions of the knapsack problem and its linear relaxation

DOI10.1134/S1064230709060070zbMath1198.49005OpenAlexW2000233350MaRDI QIDQ1956930

I. Kh. Sigal, N. N. Galim'yanova, Alexander Korbut

Publication date: 24 September 2010

Published in: Journal of Computer and Systems Sciences International (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064230709060070

zbMATH Keywords

asymptotic behaviorlinear and integer knapsack problemsone-dimensional and multi-dimensional knapsack problems with Boolean variables

Mathematics Subject Classification ID

Integer programming (90C10) Existence theories for free problems in two or more independent variables (49J10)

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Greedy algorithms for the minimization knapsack problem: average behavior
• The average behaviour of greedy algorithms for the knapsack problem: general distributions

This page was built for publication: Ratios of optimal values of objective functions of the knapsack problem and its linear relaxation