| Article ID: | iaor19961325 |
| Country: | Netherlands |
| Volume: | 16 |
| Issue: | 4 |
| Start Page Number: | 183 |
| End Page Number: | 189 |
| Publication Date: | Nov 1994 |
| Journal: | Operations Research Letters |
| Authors: | Goemans Michel X., Williamson David P. |
Building on work of Imielinska, Kalantari and Khachiyan, the authors show how to find approximte solutions for a class of NP-hard minimum-cost graph problems using only edges of a minimum-cost spanning tree. Some consequences of this work are fast 2-approximation algorithms for the 2-matching problem and its variants, as well as for simple location-routing problems.