A factor 1/2 approximation algorithm for two-stage stochastic matching problems

被引：18

作者：

Kong, N ^{[1
]}

Schaefer, AJ ^{[1
]}

机构：

[1] Univ Pittsburgh, Dept Ind Engn, Pittsburgh, PA 15261 USA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2006年 / 172卷 / 03期

基金：

美国国家科学基金会;

关键词：

stochastic programming; approximation algorithms; matching; combinatorial optimization;

D O I：

10.1016/j.ejor.2004.10.011

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NP-complete. We give a factor 1/2 approximation algorithm and prove its correctness. We also provide a tight example to show the bound given by the algorithm is exactly 1/2. Computational results on some two-stage stochastic bipartite matching instances indicate that the performance of the approximation algorithm appears to be substantially better than its worst-case performance. (c) 2004 Elsevier B.V. All rights reserved.

引用

页码：740 / 746

页数：7

共 50 条

[41] Discrete Approximation and Convergence Analysis for a Class of Decision-Dependent Two-Stage Stochastic Linear Programs
Jiang, Jie
Chen, Zhi-Ping
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2024, 12 (03) : 649 - 679
[42] ASYMPTOTIC RESULTS OF STOCHASTIC DECOMPOSITION FOR TWO-STAGE STOCHASTIC QUADRATIC PROGRAMMING
Liu, Junyi
Sen, Suvrajeet
SIAM JOURNAL ON OPTIMIZATION, 2020, 30 (01) : 823 - 852
[43] 1-APPROXIMATION ALGORITHM FOR BOTTLENECK DISJOINT PATH MATCHING
DATTA, AK
SEN, RK
INFORMATION PROCESSING LETTERS, 1995, 55 (01) : 41 - 44
[44] Two-Stage Stochastic Variational Inequality Arising from Stochastic Programming
Min Li
Chao Zhang
Journal of Optimization Theory and Applications, 2020, 186 : 324 - 343
[45] Inexact stochastic mirror descent for two-stage nonlinear stochastic programs
Vincent Guigues
Mathematical Programming, 2021, 187 : 533 - 577
[46] Inexact stochastic mirror descent for two-stage nonlinear stochastic programs
Guigues, Vincent
MATHEMATICAL PROGRAMMING, 2021, 187 (1-2) : 533 - 577
[47] A note on scenario reduction for two-stage stochastic programs
Heitsch, Holger
Roemisch, Werner
OPERATIONS RESEARCH LETTERS, 2007, 35 (06) : 731 - 738
[48] Two-Stage Stochastic Variational Inequality Arising from Stochastic Programming
Li, Min
Zhang, Chao
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2020, 186 (01) : 324 - 343
[49] A two-stage stochastic unit commitment with electricity derivatives
Siriariyaporn, V.
Sparrow, F. T.
Gotham, D. J.
2006 38TH ANNUAL NORTH AMERICAN POWER SYMPOSIUM, NAPS-2006 PROCEEDINGS, 2006, : 431 - +
[50] Stochastic ε-feaseble direction approach for two-stage SLP
Sakalauskas, Leonidas
Zilinskas, Kestutis
20TH INTERNATIONAL CONFERENCE, EURO MINI CONFERENCE CONTINUOUS OPTIMIZATION AND KNOWLEDGE-BASED TECHNOLOGIES, EUROPT'2008, 2008, : 204 - +

← 1 2 3 4 5 →