Phase transition in the knapsack problem

2018/06/26 by Nitin Yadav, Carsten Murawski, Yadav, Nitin +5
Computer Science · Decision Sciences · Engineering · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1806.10244

openalex publication_date 2018/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We examine the phase transition phenomenon for the Knapsack problem from both a computational and a human perspective. We first provide, via an empirical and a theoretical analysis, a characterization of the phenomenon in terms of two instance properties; normalised capacity and normalised profit. Then, we show evidence that average time spent by human decision makers in solving an instance peaks near the phase transition. Given the ubiquity of the Knapsack problem in every-day life, a better understanding of its structure can improve our understanding not only of computational techniques but also of human behavior, including the use and development of heuristics and occurrence of biases.

Related

• Explaining the Ubiquity of Phase Transitions in Decision Problems
• Large W limit of the knapsack problem
• 2+p-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition
• Lower bound of computational complexity of knapsack problems
• Cascading-Tree Algorithm for the 0-1 Knapsack Problem (In Memory of Heiner Müller-Merbach, a Former President of IFORS)