Partitioning heuristics for two geometric maximization problems

DOI10.1016/0167-6377(84)90059-2MaRDI QIDQ800827zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dyer, Alan Frieze, Colin McDiarmid

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)

Recommendations

• A partitioning algorithm for minimum weighted Euclidean matching
• Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
• On the weighted Euclidean matching problem in R^d
• Stochastic analysis of partitioning algorithms for matching problems
• Solving a "Hard" problem to approximate an "Easy" one

Cites work

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

Cited in

(8)

• A concentration inequality for the facility location problem
• Euclidean maximum matchings in the plane -- local to global
• Euclidean matching problems and the metropolis algorithm
• A quantization framework for smoothed analysis of Euclidean optimization problems
• Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
• Euclidean maximum matchings in the plane -- local to global
• A partitioning algorithm for minimum weighted Euclidean matching
• On the Euclidean assignment problem

This page was built for publication: Partitioning heuristics for two geometric maximization problems

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