Application of statistical mechanics to NP-complete problems in combinatorial optimisation
From MaRDI portal
Publication:3744206
DOI10.1088/0305-4470/19/9/033zbMath0606.05064OpenAlexW1965121855MaRDI QIDQ3744206
Philip W. Anderson, Yaotian Fu
Publication date: 1986
Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1088/0305-4470/19/9/033
Analysis of algorithms and problem complexity (68Q25) Classical equilibrium statistical mechanics (general) (82B05) Graph theory (05C99)
Related Items (32)
Network bipartitioning in the anti-communicability Euclidean space ⋮ On independent sets in random graphs ⋮ Disordered systems insights on computational hardness ⋮ Average optimal cost for the Euclidean TSP in one dimension ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ The demon algorithm ⋮ Random walks and orthogonal functions associated with highly symmetric graphs ⋮ When are networks truly modular? ⋮ Increasing the attraction area of the global minimum in the binary optimization problem ⋮ MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass ⋮ The marginally stable Bethe lattice spin glass revisited ⋮ Combining simulated annealing with local search heuristics ⋮ Maximum independent sets on random regular graphs ⋮ Landscapes and their correlation functions ⋮ Optimal segmentation of directed graph and the minimum number of feedback arcs ⋮ An accelerated procedure for solving binary optimization problems ⋮ Graph clustering with Boltzmann machines ⋮ Bipartitioning of directed and mixed random graphs ⋮ Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph. ⋮ The random quadratic assignment problem ⋮ Typical performance of approximation algorithms for NP-hard problems ⋮ Quantum Monte Carlo annealing with multi-spin dynamics ⋮ Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ The Shape of a Local Minimum and the Probability of its Detection in Random Search ⋮ Application of the clipping procedure to the binary minimization of a quadratic functional ⋮ Analytic constant thermodynamic speed-cooling strategies in simulated annealing ⋮ Neutrality in fitness landscapes. ⋮ On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ The peculiar phase structure of random graph bisection ⋮ Fixed-point attractors in analog neural computation
This page was built for publication: Application of statistical mechanics to NP-complete problems in combinatorial optimisation
