Partitioning heuristics for two geometric maximization problems
From MaRDI portal
Publication:800827
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
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