Partitioning heuristics for two geometric maximization problems

DOI10.1016/0167-6377(84)90059-2zbMath0551.90065OpenAlexW2021934173WikidataQ56324191 ScholiaQ56324191MaRDI QIDQ800827

Colin J. H. McDiarmid, Martin Dyer, Alan M. Frieze

Publication date: 1984

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90059-2

zbMATH Keywords

geometric maximizationlinear-time partitioning heuristics

Mathematics Subject Classification ID

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

Related Items

Euclidean maximum matchings in the plane -- local to global, Euclidean matching problems and the metropolis algorithm, On the Euclidean assignment problem, A concentration inequality for the facility location problem, A quantization framework for smoothed analysis of Euclidean optimization problems

Cites Work

• A partitioning algorithm for minimum weighted Euclidean matching
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The Euclidean traveling salesman problem is NP-complete
• A Dynamic Programming Approach to Sequencing Problems
• A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• Probability Inequalities for Sums of Bounded Random Variables
• Maximum matching and a polyhedron with 0,1-vertices