Improved bounds in stochastic matching and optimization

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

doi:10.4230/LIPIcs.APPROX-RANDOM.2015.124

Improved bounds in stochastic matching and optimization

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

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, Grandoni, and Mukherjee [1], to 3.224; we also present improvements on Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra [2] for hypergraph matching and for relaxed versions of the problem. In the context of stochastic optimization, we improve upon the sampling bounds of Charikar, Chekuri, and Pál [3].

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
Editors	Naveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	124-134
Number of pages	11
ISBN (Electronic)	9783939897897
DOIs	https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.124
State	Published - Aug 1 2015
Externally published	Yes
Event	18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 - Princeton, United States Duration: Aug 24 2015 → Aug 26 2015

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	40
ISSN (Print)	1868-8969

Conference

Conference	18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
Country/Territory	United States
City	Princeton
Period	8/24/15 → 8/26/15

All Science Journal Classification (ASJC) codes

Software

Keywords

Approximation algorithms
Sampling complexity
Stochastic matching

Access to Document

10.4230/LIPIcs.APPROX-RANDOM.2015.124

Cite this

Baveja, A., Chavan, A., Nikiforov, A., Srinivasan, A., & Xu, P. (2015). Improved bounds in stochastic matching and optimization. In N. Garg, K. Jansen, A. Rao, & J. D. P. Rolim (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015 (pp. 124-134). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 40). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.124

Baveja, Alok ; Chavan, Amit ; Nikiforov, Andrei et al. / Improved bounds in stochastic matching and optimization. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. editor / Naveen Garg ; Klaus Jansen ; Anup Rao ; Jose D. P. Rolim. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. pp. 124-134 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{bc8816e6e239495ba2e3acfbb1ef5e9f,

title = "Improved bounds in stochastic matching and optimization",

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, Grandoni, and Mukherjee [1], to 3.224; we also present improvements on Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra [2] for hypergraph matching and for relaxed versions of the problem. In the context of stochastic optimization, we improve upon the sampling bounds of Charikar, Chekuri, and P{\'a}l [3].",

keywords = "Approximation algorithms, Sampling complexity, Stochastic matching",

author = "Alok Baveja and Amit Chavan and Andrei Nikiforov and Aravind Srinivasan and Pan Xu",

note = "Publisher Copyright: {\textcopyright} Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu.; 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 ; Conference date: 24-08-2015 Through 26-08-2015",

year = "2015",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.APPROX-RANDOM.2015.124",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "124--134",

editor = "Naveen Garg and Klaus Jansen and Anup Rao and Rolim, {Jose D. P.}",

booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015",

address = "Germany",

}

Baveja, A, Chavan, A, Nikiforov, A, Srinivasan, A & Xu, P 2015, Improved bounds in stochastic matching and optimization. in N Garg, K Jansen, A Rao & JDP Rolim (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Leibniz International Proceedings in Informatics, LIPIcs, vol. 40, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 124-134, 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015, Princeton, United States, 8/24/15. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.124

Improved bounds in stochastic matching and optimization. / Baveja, Alok; Chavan, Amit; Nikiforov, Andrei et al.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. ed. / Naveen Garg; Klaus Jansen; Anup Rao; Jose D. P. Rolim. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2015. p. 124-134 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 40).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Improved bounds in stochastic matching and optimization

AU - Baveja, Alok

AU - Chavan, Amit

AU - Nikiforov, Andrei

AU - Srinivasan, Aravind

AU - Xu, Pan

N1 - Publisher Copyright: © Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu.

PY - 2015/8/1

Y1 - 2015/8/1

N2 - 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, Grandoni, and Mukherjee [1], to 3.224; we also present improvements on Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra [2] for hypergraph matching and for relaxed versions of the problem. In the context of stochastic optimization, we improve upon the sampling bounds of Charikar, Chekuri, and Pál [3].

AB - 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, Grandoni, and Mukherjee [1], to 3.224; we also present improvements on Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra [2] for hypergraph matching and for relaxed versions of the problem. In the context of stochastic optimization, we improve upon the sampling bounds of Charikar, Chekuri, and Pál [3].

KW - Approximation algorithms

KW - Sampling complexity

KW - Stochastic matching

UR - http://www.scopus.com/inward/record.url?scp=84958533838&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958533838&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2015.124

DO - 10.4230/LIPIcs.APPROX-RANDOM.2015.124

M3 - Conference contribution

AN - SCOPUS:84958533838

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 124

EP - 134

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015

A2 - Garg, Naveen

A2 - Jansen, Klaus

A2 - Rao, Anup

A2 - Rolim, Jose D. P.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015

Y2 - 24 August 2015 through 26 August 2015

ER -

Baveja A, Chavan A, Nikiforov A, Srinivasan A, Xu P. Improved bounds in stochastic matching and optimization. In Garg N, Jansen K, Rao A, Rolim JDP, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2015. p. 124-134. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.APPROX-RANDOM.2015.124

Improved bounds in stochastic matching and optimization

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this