Phase transition in the knapsack problem
This work provides insights into both computational methods and human behavior for a widely applicable optimization problem.
The study characterized the phase transition in the Knapsack problem using normalized capacity and profit, and found that human decision-making time peaks near this transition.
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.