Logo of Humboldt-Universität zu BerlinLogo of Humboldt-Universität zu Berlin
edoc-Server
Open-Access-Publikationsserver der Humboldt-Universität
de|en
Header image: facade of Humboldt-Universität zu Berlin
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2004
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2004
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
All of edoc-ServerCommunity & CollectionTitleAuthorSubjectThis CollectionTitleAuthorSubject
PublishLoginRegisterHelp
StatisticsView Usage Statistics
View Item 
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2004
  • View Item
  • edoc-Server Home
  • Elektronische Zeitschriften
  • Stochastic Programming E-print Series (SPEPS)
  • Volume 2004
  • View Item
2004-02-19Buch DOI: 10.18452/8312
A factor 1/2 approximation algorithm for a class of two-stage stochastic mixed-integer programs
Kong, Nan
Schaefer, Andrew J.
Abstract 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.
Files in this item
Thumbnail
5.pdf — Adobe PDF — 161.0 Kb
MD5: a9639c5ff5a0c664e329fd71d0cf1407
Cite
BibTeX
EndNote
RIS
InCopyright
Details
DINI-Zertifikat 2019OpenAIRE validatedORCID Consortium
Imprint Policy Contact Data Privacy Statement
A service of University Library and Computer and Media Service
© Humboldt-Universität zu Berlin
 
DOI
10.18452/8312
Permanent URL
https://doi.org/10.18452/8312
HTML
<a href="https://doi.org/10.18452/8312">https://doi.org/10.18452/8312</a>