Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation

被引：10

作者：

Escoffier, Bruno ^{[1
]}

Gourves, Laurent ^{[1
]}

Monnot, Jerome ^{[1
]}

Spanjaard, Olivier ^{[2
]}

机构：

[1] Univ Paris 09, CNRS, LAMSADE, F-75775 Paris 16, France

[2] Univ Paris 06, CNRS, LIP6, F-75016 Paris, France

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2010年 / 205卷 / 01期

关键词：

Stochastic programming; Approximation algorithms; Matching; Maximum spanning tree; Combinatorial optimization; OPTIMIZATION; UNCERTAINTY; ALGORITHMS;

D O I：

10.1016/j.ejor.2009.12.004

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This article deals with the two-stage stochastic model, which aims at explicitly taking into account uncertainty in optimization problems, that Kong and Schaefer have recently studied for the maximum weight matching problem [N. Kong, A.J. Schaefer, A factor 1/2 approximation algorithm for two-stage stochastic matching problems, European Journal of Operational Research 172(3) (2006) 740-746]. They have proved that the problem is NP-hard, and they have provided a factor 1/2 approximation algorithm. We further Study this problem and strengthen the hardness results, slightly improve the approximation ratio and exhibit some polynomial cases. We similarly tackle the maximum weight spanning tree problem in the two-stage setting. Finally, we make numerical experiments on randomly generated instances to compare the quality of several interesting heuristics. (C) 2009 Elsevier B.V. All rights reserved,

引用

页码：19 / 30

页数：12

共 14 条

[1] [Anonymous], 2004, P 36 ANN ACM S THEOR
[2] [Anonymous], 1997, Introduction to stochastic programming
[3] On the random 2-stage minimum spanning tree
Flaxman, AD
Frieze, A
Krivelevich, M
[J]. RANDOM STRUCTURES & ALGORITHMS, 2006, 28 (01) : 24 - 36
[4] Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[5] GONDRAN M, 1979, GRAPHES ALGORITHMES
[6] Gupta A, 2005, LECT NOTES COMPUT SC, V3624, P86
[7] Immorlica N., 2004, P 15 ANN ACM SIAM S, P691
[8] Kall P, 1994, Stochastic Programming
[9] Katriel I, 2007, LECT NOTES COMPUT SC, V4596, P171
[10] König D, 1915, MATH ANN, V77, P453

← 1 2 →