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

DOI10.1287/ijoc.8.1.29zbMath0855.90074OpenAlexW2057656719MaRDI QIDQ4888174

Michel X. Goemans, David P. Williamson

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

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

Related Items (1)

An approximation algorithm for minimum-cost vertex-connectivity problems

Uses Software

• TSPLIB

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