Document Open Access Logo

Improved Bounds in Stochastic Matching and Optimization

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.124.pdf
  • Filesize: 483 kB
  • 11 pages

Document Identifiers

Author Details

Alok Baveja
Amit Chavan
Andrei Nikiforov
Aravind Srinivasan
Pan Xu

Cite AsGet BibTex

Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu. Improved Bounds in Stochastic Matching and Optimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 124-134, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.124

Abstract

We consider two fundamental problems in stochastic optimization: approximation algorithms for stochastic matching, and sampling bounds in the black-box model. For the former, we improve the current-best bound of 3.709 due to Adamczyk et al. (2015), to 3.224; we also present improvements on Bansal et al. (2012) for hypergraph matching and for relaxed versions of the problem. In the context of stochastic optimization, we improve upon the sampling bounds of Charikar et al. (2005).
Keywords
  • stochastic matching
  • approximation algorithms
  • sampling complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee. Improved approximation algorithms for stochastic matching. CoRR, abs/1505.01439, 2015. Google Scholar
  2. Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra. When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica, 63(4):733-762, 2012. Google Scholar
  3. Moses Charikar, Chandra Chekuri, and Martin Pál. Sampling bounds for stochastic optimization. In Proceedings of the 8th International Workshop on Approximation, Randomization and Combinatorial Optimization Problems, and Proceedings of the 9th International Conference on Randamization and Computation: Algorithms and Techniques, APPROX'05/RANDOM'05, pages 257-269. Springer-Verlag, 2005. Google Scholar
  4. Ning Chen, Nicole Immorlica, Anna R Karlin, Mohammad Mahdian, and Atri Rudra. Approximating matches made in heaven. Automata, Languages and Programming, pages 266-278, 2009. Google Scholar
  5. Brian C Dean, Michel X Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research, 33(4):945-964, 2008. Google Scholar
  6. Zoltán Füredi, Jeff Kahn, and Paul D. Seymour. On the fractional matching polytope of a hypergraph. Combinatorica, 13(2):167-180, 1993. Google Scholar
  7. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM), 53(3):324-360, 2006. Google Scholar
  8. Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combinatorial optimization problems. In SODA, pages 942-951, 2008. Google Scholar
  9. Anupam Gupta and Amit Kumar. A constant-factor approximation for stochastic steiner forest. In STOC, pages 659-668, 2009. Google Scholar
  10. Anupam Gupta, R Ravi, and Amitabh Sinha. An edge in time saves nine: Lp rounding approximation algorithms for stochastic network design. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 218-227. IEEE, 2004. Google Scholar
  11. Nicole Immorlica, David Karger, Maria Minkoff, and Vahab S Mirrokni. On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 691-700. Society for Industrial and Applied Mathematics, 2004. Google Scholar
  12. Anton J Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2):479-502, 2002. Google Scholar
  13. Jeff Linderoth, Alexander Shapiro, and Stephen Wright. The empirical behavior of sampling methods for stochastic programming. Annals of Operations Research, 142(1):215-241, 2006. Google Scholar
  14. Andrzej Ruszczynski and Alexander Shapiro. Stochastic programming. Handbooks in operations research and management science, 2003. Google Scholar
  15. Alexander Shapiro. Monte Carlo sampling methods. Handbooks in operations research and management science, 10:353-425, 2003. Google Scholar
  16. David B Shmoys and Chaitanya Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. Journal of the ACM (JACM), 53(6):978-1012, 2006. Google Scholar
  17. A. Srinivasan. Approximation algorithms for stochastic and risk-averse optimization. In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 1305-1313, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact