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
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
