Greedy algorithms for a class of knapsack problems with binary weights



In this article we identify a class of two-dimensional knapsack problems and related three-criteria unconstrained combinatorial optimization problems that can be solved in polynomial time by greedy algorithms. For the latter problem, the proposed algorithm explores the connectedness of the set of efficient solutions. Extensive computational results show that this approach can solve the three-criteria problem up to one million items in half an hour.

PDF File

Cited by

Year 2014 : 4 citations

 N Tcholtchev, I Schieferdecker, Framework for ensuring runtime stability of control loops in multi-agent networked environments, Transactions on Computational Science …, 2014

 A Rong, JR Figueira, Dynamic programming algorithms for the bi-objective integer knapsack problem, European Journal of Operational Research, 2014

 C Changdar, GS Mahapatra, RK Pal, An improved genetic algorithm based approach to solve constrained knapsack problem in fuzzy environment, Expert Systems with Applications, 2014

 N NikoliÄ?, I GrujičiÄ?, N MladenoviÄ?, A large neighbourhood search heuristic for covering designs, IMA Journal of Management Mathematics, 2014

Year 2013 : 4 citations

 A Rong, JR Figueira, A reduction dynamic programming algorithm for the bi-objective integer knapsack problem, European Journal of Operational Research, 2013

 GH Velde, Streamlining storage of test equipment at siemens Hengelo: a capacity based approach, Publication/NA, 2013

 RC Chen, YD Lin, CM Tsai, H Jiang, Constructing a Diet Recommendation System Based on Fuzzy Rules and Knapsack Method, Recent Trends in Applied Artificial …, 2013

 A Rong, K Klamroth, J Rui Figueira, Multicriteria 0-1 knapsack problems with< i> k-min objectives, Computers & Operations Research, 2013

Year 2012 : 2 citations

 W Liu, G Liu, [CITATION][C] Genetic Algorithm with Directional Mutation Based on Greedy Strategy for Large-scale 0-1 Knapsack Problems., International Journal of Advancements in Computing …, 2012

 J Peng, B Zhang, Knapsack problem with uncertain weights and values, Publication/NA, 2012

Year 2010 : 1 citations

 J Gorski, L Paquete, On a particular case of the multi-criteria unconstrained optimization problem, Electronic Notes in Discrete Mathematics, 2010