Improved Bounds in Stochastic Matching and Optimization

Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, Pan Xu

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a classical problem in combinatorial optimization. Modern stochastic versions of this problem model problems in kidney exchange, for instance. We improve upon the current-best approximation bound of 3.709 for stochastic matching due to Adamczyk et al. (in: Algorithms-ESA 2015, Springer, Berlin, 2015) to 3.224; we also present improvements on Bansal et al. (Algorithmica 63(4):733–762, 2012) for hypergraph matching and for relaxed versions of the problem. These results are obtained by improved analyses and/or algorithms for rounding linear-programming relaxations of these problems.

Original languageEnglish (US)
Pages (from-to)3225-3252
Number of pages28
JournalAlgorithmica
Volume80
Issue number11
DOIs
StatePublished - Nov 1 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Approximation algorithms
  • Linear programming
  • Randomized algorithms
  • Stochastic optimization

Fingerprint

Dive into the research topics of 'Improved Bounds in Stochastic Matching and Optimization'. Together they form a unique fingerprint.

Cite this