Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances

DOI10.1287/IJOC.8.1.29MaRDI QIDQ4888174zbMATH OpenOpenAlexFDO

Authors David P. Williamson, Michel X. Goemans

Publication date 28 October 1996

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.8.1.29

zbMATH Keywords

2-approximation algorithmEuclidean minimum-cost perfect matching

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 1003267
• scientific article; zbMATH DE number 1305475
• Approximation algorithms for bipartite matching with metric and geometric costs
• A Monte Carlo solution to the minimal Euclidean matching
• New primal and dual matching heuristics

Cited in

(9)

• Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs
• Approximation algorithms for the Euclidean bipartite TSP
• scientific article; zbMATH DE number 1003267 (Why is no real title available?)
• A Monte Carlo solution to the minimal Euclidean matching
• Euclidean matching problems and the metropolis algorithm
• On the weighted Euclidean matching problem in R^d
• scientific article; zbMATH DE number 1446757 (Why is no real title available?)
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• An approximation algorithm for minimum-cost vertex-connectivity problems

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances

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