APPROXIMATING MINIMUM-COST GRAPH PROBLEMS WITH SPANNING TREE EDGES

Authors
GOEMANS MX WILLIAMSON DP
Citation
Mx. Goemans et Dp. Williamson, APPROXIMATING MINIMUM-COST GRAPH PROBLEMS WITH SPANNING TREE EDGES, Operations research letters, 16(4), 1994, pp. 183-189
Citations number
14
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
16
Issue
4
Year of publication
1994
Pages
183 - 189
Database
ISI
SICI code
0167-6377(1994)16:4<183:AMGPWS>2.0.ZU;2-K
Abstract
Building on work of Imielinska, Kalantari and Khachiyan, we show how t o find approximate solutions for a class of NP-hard minimum-cost graph problems using only edges of a minimum-cost spanning tree. Some conse quences of this work are fast 2-approximation algorithms for the 2-mat ching problem and its variants, as well as for simple location-routing problems.