Optimization of chance-constrained submodular functions

Benjamin Doerr; Carola Doerr; Aneta Neumann; Frank Neumann; Andrew M. Sutton

Optimization of chance-constrained submodular functions

Benjamin Doerr, Carola Doerr, Aneta Neumann, Frank Neumann, Andrew M. Sutton

Computer Science (Duluth)

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

21 Scopus citations

Abstract

Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a first analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.

Original language	English (US)
Title of host publication	AAAI 2020 - 34th AAAI Conference on Artificial Intelligence
Publisher	AAAI press
Pages	1460-1467
Number of pages	8
ISBN (Electronic)	9781577358350
State	Published - 2020
Event	34th AAAI Conference on Artificial Intelligence, AAAI 2020 - New York, United States Duration: Feb 7 2020 → Feb 12 2020

Publication series

Name	AAAI 2020 - 34th AAAI Conference on Artificial Intelligence

Conference

Conference	34th AAAI Conference on Artificial Intelligence, AAAI 2020
Country/Territory	United States
City	New York
Period	2/7/20 → 2/12/20

Bibliographical note

Funding Information:
This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium ”Un-

Funding Information:
This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium”Unlocking Complex Resources through Lean Processing”, by the Paris Ile-de-France region, and by a public grant as part of the Investissement d'avenir project, reference ANR-11LABX-0056-LMH, LabEx LMH.

Publisher Copyright:
Copyright © 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

OpenUrl availability

Full text

Cite this

@inproceedings{09e127bf3c5a41cd8cda35eb8c13099f,

title = "Optimization of chance-constrained submodular functions",

abstract = "Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a first analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.",

author = "Benjamin Doerr and Carola Doerr and Aneta Neumann and Frank Neumann and Sutton, {Andrew M.}",

note = "Funding Information: This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium ”Un- Funding Information: This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium”Unlocking Complex Resources through Lean Processing”, by the Paris Ile-de-France region, and by a public grant as part of the Investissement d'avenir project, reference ANR-11LABX-0056-LMH, LabEx LMH. Publisher Copyright: Copyright {\textcopyright} 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 34th AAAI Conference on Artificial Intelligence, AAAI 2020 ; Conference date: 07-02-2020 Through 12-02-2020",

year = "2020",

language = "English (US)",

series = "AAAI 2020 - 34th AAAI Conference on Artificial Intelligence",

publisher = "AAAI press",

pages = "1460--1467",

booktitle = "AAAI 2020 - 34th AAAI Conference on Artificial Intelligence",

}

TY - GEN

T1 - Optimization of chance-constrained submodular functions

AU - Doerr, Benjamin

AU - Doerr, Carola

AU - Neumann, Aneta

AU - Neumann, Frank

AU - Sutton, Andrew M.

N1 - Funding Information: This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium ”Un- Funding Information: This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium”Unlocking Complex Resources through Lean Processing”, by the Paris Ile-de-France region, and by a public grant as part of the Investissement d'avenir project, reference ANR-11LABX-0056-LMH, LabEx LMH. Publisher Copyright: Copyright © 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

PY - 2020

Y1 - 2020

N2 - Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a first analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.

AB - Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a first analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.

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

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

M3 - Conference contribution

AN - SCOPUS:85091272233

T3 - AAAI 2020 - 34th AAAI Conference on Artificial Intelligence

SP - 1460

EP - 1467

BT - AAAI 2020 - 34th AAAI Conference on Artificial Intelligence

PB - AAAI press

T2 - 34th AAAI Conference on Artificial Intelligence, AAAI 2020

Y2 - 7 February 2020 through 12 February 2020

ER -

Optimization of chance-constrained submodular functions

Abstract

Publication series

Conference

Bibliographical note

OpenUrl availability

Other files and links

Fingerprint

Cite this