1 Search Results for "Baveja, Alok"

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.124
Improved Bounds in Stochastic Matching and Optimization

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

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

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).
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{baveja_et_al:LIPIcs.APPROX-RANDOM.2015.124,
  author =	{Baveja, Alok and Chavan, Amit and Nikiforov, Andrei and Srinivasan, Aravind and Xu, Pan},
  title =	{{Improved Bounds in Stochastic Matching and Optimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{124--134},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.124},
  URN =		{urn:nbn:de:0030-drops-52991},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.124},
  annote =	{Keywords: stochastic matching, approximation algorithms, sampling complexity}
}
  • Refine by Author
  • 1 Baveja, Alok
  • 1 Chavan, Amit
  • 1 Nikiforov, Andrei
  • 1 Srinivasan, Aravind
  • 1 Xu, Pan

  • Refine by Classification

  • Refine by Keyword
  • 1 approximation algorithms
  • 1 sampling complexity
  • 1 stochastic matching

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

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