Statistical mechanics analysis of generalized multi-dimensional knapsack problems

DOI10.1088/1751-8121/AC8381MaRDI QIDQ5870449zbMATH OpenOpenAlexFDO

Authors Yuta Nakamura, Takashi Takahashi, Yoshiyuki Kabashima

Publication date 9 January 2023

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2201.06807

zbMATH Keywords

knapsack problemoptimization problemreplica methodbelief propagationcavity method

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX) Mathematical programming (90Cxx)

Recommendations

• A statistical analysis of the knapsack problem
• Statistical mechanics of the knapsack problem
• Greedy algorithm for the general multidimensional knapsack problem
• Statistical mechanics of the multi-constraint continuous knapsack problem
• The multidimensional knapsack problem: structure and algorithms

Cites work

• A CDMA multiuser detection algorithm on the basis of belief propagation
• A hybrid algorithm for the unbounded knapsack problem
• A typology of cutting and packing problems
• Computational Complexity
• Computational aspects of hard knapsack problems.
• Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables
• Discrete dynamic programming and capital allocation
• Expectation consistent approximate inference
• Greedy algorithm for the general multidimensional knapsack problem
• Information, Physics, and Computation
• Optimization of mean-field spin glasses
• Ottimizzazione Combinatoria
• Replica symmetry instability in perceptron models
• Revisiting \textit{Where are the hard knapsack problems?} via instance space analysis
• Statistical mechanics of the knapsack problem
• Statistical mechanics of the multi-constraint continuous knapsack problem
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Where are the hard knapsack problems?

Cited in

(3)

• Statistical mechanics of the multi-constraint continuous knapsack problem
• Computing Optimized Path Integrals for Knapsack Feasibility
• Statistical mechanics analysis of general multi-dimensional knapsack problems

Describes a project that uses

Uses Software

• OR-tools

This page was built for publication: Statistical mechanics analysis of generalized multi-dimensional knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5870449)