Stochastic packing integer programs with few queries

Takanori Maehara; Yutaro Yamaguchi

doi:10.1137/1.9781611975031.21

Stochastic packing integer programs with few queries

Takanori Maehara, Yutaro Yamaguchi

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

19 Citations (Scopus)

Abstract

We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems.

Original language	English
Title of host publication	29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Editors	Artur Czumaj
Publisher	Association for Computing Machinery
Pages	293-310
Number of pages	18
ISBN (Electronic)	9781611975031
DOIs	https://doi.org/10.1137/1.9781611975031.21
Publication status	Published - 2018
Externally published	Yes
Event	29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States Duration: Jan 7 2018 → Jan 10 2018

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference	29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/Territory	United States
City	New Orleans
Period	1/7/18 → 1/10/18

All Science Journal Classification (ASJC) codes

Software
Mathematics(all)

Access to Document

10.1137/1.9781611975031.21

Cite this

Stochastic packing integer programs with few queries. / Maehara, Takanori; Yamaguchi, Yutaro.
29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. ed. / Artur Czumaj. Association for Computing Machinery, 2018. p. 293-310 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

Maehara, T & Yamaguchi, Y 2018, Stochastic packing integer programs with few queries. in A Czumaj (ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 293-310, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, United States, 1/7/18. https://doi.org/10.1137/1.9781611975031.21

@inproceedings{b8b999fc863f4527a7a41d31f8b8c33a,

title = "Stochastic packing integer programs with few queries",

abstract = "We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems.",

author = "Takanori Maehara and Yutaro Yamaguchi",

year = "2018",

doi = "10.1137/1.9781611975031.21",

language = "English",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "293--310",

editor = "Artur Czumaj",

booktitle = "29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018",

}

TY - GEN

T1 - Stochastic packing integer programs with few queries

AU - Maehara, Takanori

AU - Yamaguchi, Yutaro

PY - 2018

Y1 - 2018

N2 - We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems.

AB - We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems.

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

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

U2 - 10.1137/1.9781611975031.21

DO - 10.1137/1.9781611975031.21

M3 - Conference contribution

AN - SCOPUS:85045539366

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 293

EP - 310

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -

Stochastic packing integer programs with few queries

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this