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 条
  • [21] On sample average approximation for two-stage stochastic programs without relatively complete recourse
    Rui Chen
    James Luedtke
    Mathematical Programming, 2022, 196 : 719 - 754
  • [22] The Decomposition Method for Two-Stage Stochastic Linear Programming Problems with Quantile Criterion
    Zhenevskaya, I. D.
    Naumov, A. V.
    AUTOMATION AND REMOTE CONTROL, 2018, 79 (02) : 229 - 240
  • [23] Two-stage stochastic programming problems involving interval discrete random variables
    Suresh Kumar Barik
    Mahendra Prasad Biswal
    Debashish Chakravarty
    OPSEARCH, 2012, 49 (3) : 280 - 298
  • [24] Two-stage stochastic programming problems involving interval discrete random variables
    Barik, Suresh
    Biswal, Mahendra
    Chakravarty, Debashish
    OPSEARCH, 2012, 49 (03) : 280 - 298
  • [25] State-Variable Modeling for a Class of Two-Stage Stochastic Optimization Problems
    Doulabi, Hossein Hashemi
    Ahmed, Shabbir
    Nemhauser, George
    INFORMS JOURNAL ON COMPUTING, 2022, 34 (01) : 354 - 369
  • [26] Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios
    Ota, Matheus J.
    Fukasawa, Ricardo
    OPERATIONS RESEARCH, 2024,
  • [27] Two-stage stochastic programming problems involving multi-choice parameters
    Barik, S. K.
    Biswal, M. P.
    Chakravarty, D.
    APPLIED MATHEMATICS AND COMPUTATION, 2014, 240 : 109 - 114
  • [28] The Decomposition Method for Two-Stage Stochastic Linear Programming Problems with Quantile Criterion
    I. D. Zhenevskaya
    A. V. Naumov
    Automation and Remote Control, 2018, 79 : 229 - 240
  • [29] Fast scenario reduction by conditional scenarios in two-stage stochastic MILP problems
    Beltran-Royo, C.
    OPTIMIZATION METHODS & SOFTWARE, 2022, 37 (01) : 23 - 44
  • [30] Two-stage combinatorial optimization problems under risk
    Goerigk, Marc
    Kasperski, Adam
    Zielinski, Pawel
    THEORETICAL COMPUTER SCIENCE, 2020, 804 : 29 - 45
12345