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

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

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)

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

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)