APPROXIMATING MINIMUM-COST GRAPH PROBLEMS WITH SPANNING TREE EDGES

被引：16

作者：

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

共 14 条

[1]

[Anonymous], 1988, GEOMETRIC ALGORITHMS, DOI DOI 10.1007/978-3-642-97881-4

[2] MATCHING PROBLEM WITH SIDE CONDITIONS [J].

CORNUEJOLS, G ;

PULLEYBLANK, W .

DISCRETE MATHEMATICS, 1980, 29 (02) :135-159

[3]

EDMONDS J, 1970, P CALG INT C COMB ST, P82

[4] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].

FREDMAN, ML ;

TARJAN, RE .

JOURNAL OF THE ACM, 1987, 34 (03) :596-615

[5]

GABOW HN, 1993, 3RD P MPS C INT PROG, P57

[6]

GOEMANS MX, 1992, 3RD P ANN ACM SIAM S, P307

[7] A GREEDY HEURISTIC FOR A MINIMUM-WEIGHT FOREST PROBLEM [J].

IMIELINSKA, C ;

KALANTARI, B ;

KHACHIYAN, L .

OPERATIONS RESEARCH LETTERS, 1993, 14 (02) :65-71

[8] HAMILTONIAN LOCATION-PROBLEMS [J].

LAPORTE, G ;

NOBERT, Y ;

PELLETIER, P .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1983, 12 (01) :82-89

[9]

Laporte G., 1988, VEHICLE ROUTING METH, P163

[10]

Preparata F. P., 2012, COMPUTATIONAL GEOMET

← 1 2 →