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

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

Review text

Given n points randomly selected from a uniform distribution on the unit square, we describe linear-time partitioning heuristics which will construct a matching or a tour of these points. We show that the heuristics closely approximate the optimum values as \(n\to \infty\). Hence we show that the asymptotic values of the maximum matching and tour are about 0.3826n and twice this value respectively.

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)

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

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)