# Large N limit of the knapsack problem

@article{Williams2021LargeNL, title={Large N limit of the knapsack problem}, author={Mobolaji Williams}, journal={ArXiv}, year={2021}, volume={abs/2107.14080} }

In the simplest formulation of the knapsack problem, one seeks to maximize the total value of a collection of objects such that the total weight remains below a certain limit. In this work, we move from computer science to physics and formulate the knapsack problem as a statistical physics system and compute the corresponding partition function. We approximate the result in the large number limit and from this approximation develop a new algorithm for the problem. We compare the performance of… Expand

#### References

SHOWING 1-10 OF 21 REFERENCES

Where are the hard knapsack problems?

- Mathematics, Computer Science
- Comput. Oper. Res.
- 2005

The purpose of this paper is to give an overview of all recent exact solution approaches, and to show that the knapsack problem still is hard to solve for these algorithms for a variety of new test problems. Expand

Thermodynamical Approach to the Traveling Salesman Problem : An Efficient Simulation Algorithm

- 2004

We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem. The algorithm generates randomly the permutations of the stations of the traveling salesman trip,… Expand

Computational Complexity and Statistical Physics

- Computer Science
- Studies in the sciences of complexity
- 2006

Computational Complexity and Statistical Physics will serve as a standard reference and pedagogical aid to statistical physics methods in computer science, with a particular focus on phase transitions in combinatorial problems. Expand

Approximation Algorithms

- Computer Science
- Springer Berlin Heidelberg
- 2003

Covering the basic techniques used in the latest research work, the author consolidates progress made so far, including some very recent and promising results, and conveys the beauty and excitement… Expand

Knapsack Problems: Algorithms and Computer Implementations

- Computer Science
- 1990

This paper focuses on the part of the knapsack problem where the problem of bin packing is concerned and investigates the role of computer codes in the solution of this problem. Expand

The Statistical Mechanics of Phase Transitions

- Physics
- 1978

Abstract This article traces the development and study of phase transitions from late last century to the present day. We begin with a brief historical sketch and a description of the statistical… Expand

Mathematical physics : a modern introduction to Its foundations

- Mathematics
- 2013

The goal of this book is to expose the reader to the indispensable role that mathematics---often very abstract--Content for physicists and the example sections in physics this volume book. All a… Expand

SciPy 1.0: fundamental algorithms for scientific computing in Python

- Computer Science, Physics
- Nature Methods
- 2020

An overview of the capabilities and development practices of SciPy 1.0 is provided and some recent technical developments are highlighted. Expand

Parallel Distributed Processing: Explorations in the Microstructure of Cognition, vol 1: Foundations, vol 2: Psychological and Biological Models

- Medicine
- 1994

Artificial neural network research began in the early 1940s, advancing in fits and starts, until the late 1960s when Minsky and Papert published Perceptrons, in which they proved that neural networks, as then conceived, can be proved. Expand

Multidimensional Knapsack Problems

- Computer Science
- Encyclopedia of Optimization
- 2009

The invention greatly facilitates the recovery of pipeline from a deep sea bottom and can dispense with use of divers normally required heretofore. Expand