Show simple item record

dc.contributor.authorGourvès, Laurent
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorSpanjaard, Olivier
HAL ID: 14601
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2010-04-12T13:41:33Z
dc.date.available2010-04-12T13:41:33Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3935
dc.language.isoenen
dc.subjectStochastic programmingen
dc.subjectApproximation algorithmsen
dc.subjectMatchingen
dc.subjectMaximum spanning treeen
dc.subjectCombinatorial optimizationen
dc.subject.ddc003en
dc.titleTwo-stage stochastic matching and spanning tree problems: Polynomial instances and approximationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis 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.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol205en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2010-08
dc.relation.isversionofjnlpages19-30en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2009.12.004en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record