APPROXIMATING MINIMUM-COST GRAPH PROBLEMS WITH SPANNING TREE EDGES

被引：15
|
作者：
GOEMANS, MX [1 ]
WILLIAMSON, DP [1 ]
机构：
[1] CORNELL UNIV,SCH OPERAT RES & IND ENGN,ITHACA,NY 14853
来源：
OPERATIONS RESEARCH LETTERS | 1994年 / 16卷 / 04期
基金：
美国国家科学基金会;
关键词：
APPROXIMATION ALGORITHMS; COMBINATORIAL OPTIMIZATION; 2-MATCHING;
D O I：
10.1016/0167-6377(94)90067-1
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Building on work of Imielinska, Kalantari and Khachiyan, we show how to find approximate 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.
引用
收藏
页码：183 / 189
页数：7
相关论文
共 50 条
12345