Euclidean matching problems and the metropolis algorithm

DOI10.1007/BF01919172MaRDI QIDQ3727741zbMATH OpenOpenAlexFDO

Authors M. Weber, Thomas M. Liebling

Publication date 1986

Published in Zeitschrift für Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01919172

zbMATH Keywords

asymptotic behaviourcomputational resultseuclidean combinatorial optimizationgeometric probabilitylarge-scale Euclidean matchingrandomly generated problemssimulated annealing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Recommendations

• Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
• An efficient heuristic algorithm for minimum matching
• A Monte Carlo solution to the minimal Euclidean matching
• The Euclidean Matching Problem
• Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances

Cites work

• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• Cooling Schedules for Optimal Annealing
• Heuristics for planar minimum‐weight perfect metchings
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Optimization by simulated annealing
• Partitioning heuristics for two geometric maximization problems
• Paths, Trees, and Flowers
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm

Cited in

(16)

• Reconstruction of polycrystalline structures: a new application of combinatorial optimization
• A simulated annealing approach to the multiconstraint zero-one knapsack problem
• On the Euclidean assignment problem
• Quantizers ad the worst case Euclidean traveling salesman problem
• An efficient matching algorithm applied in statistical physics
• Applying tabu search with influential diversification to multiprocessor scheduling
• New primal and dual matching heuristics
• Convergence of asymptotic costs for random Euclidean matching problems
• Euclidean random matching in 2D for non-constant densities
• A concentration inequality for the facility location problem
• The Euclidean Matching Problem
• An efficient heuristic algorithm for minimum matching
• scientific article; zbMATH DE number 1202983 (Why is no real title available?)
• Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
• A quantization framework for smoothed analysis of Euclidean optimization problems
• Methods for the one-dimensional space allocation problem

This page was built for publication: Euclidean matching problems and the metropolis algorithm

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