A statistical analysis of the knapsack problem

Effect of constraint relaxation on the minimum vertex cover problem in random graphs

A statistical-mechanical study of the effect of constraint relaxation on the minimum vertex cover problem in Erdős-Rényi random graphs is presented. Using a penalty-method formulation for constraint relaxation, typical properties of solutions, including infeasible solutions that violate the constraints, are analyzed by means of the replica method and cavity method. The problem involves a competition between reducing the number of vertices to be covered and satisfying the edge constraints. The analysis under the replica-symmetric (RS) ansatz clarifies that the competition leads to degeneracies in the vertex and edge states, which determine the quantitative properties of the system, such as the cover and penalty ratios. A precise analysis of these effects improves the accuracy of RS approximation for the minimum cover ratio in the replica symmetry-breaking (RSB) region. Furthermore, the analysis based on the RS cavity method indicates that the RS/RSB boundary of the ground states with respect to the mean degree of the graphs is expanded, and the critical temperature is lowered by constraint relaxation.

Large-W limit of the knapsack problem

We formulate the knapsack problem (KP) as a statistical physics system and compute the corresponding partition function as an integral in the complex plane. The introduced formalism allows us to derive three statistical-physics-based algorithms for the KP: one based on the recursive definition of the exact partition function, another based on the large weight limit of that partition function, and a final one based on the zero-temperature limit of the second. Comparing the performances of the algorithms, we find that they do not consistently outperform (in terms of runtime and accuracy) dynamic programming, annealing, or standard greedy algorithms. However, the exact partition function is shown to reproduce the dynamic programming solution to the KP, and the zero-temperature algorithm is shown to produce a greedy solution. Therefore, although dynamic programming and greedy solutions to the KP are conceptually distinct, a statistical physics formalism introduced reveals that the large weight-constraint limit of the former leads to the latter. We conclude by discussing how to extend this formalism in order to obtain more accurate versions of the introduced algorithms and other similar combinatorial optimization problems.