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
