• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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

Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010), Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation, European Journal of Operational Research, 205, 1, p. 19-30. http://dx.doi.org/10.1016/j.ejor.2009.12.004

Type
Article accepté pour publication ou publié
Date
2010
Journal name
European Journal of Operational Research
Volume
205
Number
1
Publisher
Elsevier
Pages
19-30
Publication identifier
http://dx.doi.org/10.1016/j.ejor.2009.12.004
Metadata
Show full item record
Author(s)
Gourvès, Laurent
Escoffier, Bruno
Spanjaard, Olivier
Monnot, Jérôme cc
Abstract (EN)
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 View the MathML source 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.
Subjects / Keywords
Stochastic programming; Approximation algorithms; Matching; Maximum spanning tree; Combinatorial optimization

Related items

Showing items related by title and author.

  • Thumbnail
    The Price of Optimum: Complexity and Approximation for a Matching Game 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2017) Article accepté pour publication ou publié
  • Thumbnail
    Some tractable instances of interval data minmax regret problems: bounded distance from triviality 
    Escoffier, Bruno; Monnot, Jérôme; Spanjaard, Olivier (2008) Communication / Conférence
  • Thumbnail
    Some tractable instances of interval data minmax regret problems 
    Escoffier, Bruno; Monnot, Jérôme; Spanjaard, Olivier (2008) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo