1 Search Results for "Tang, Shaojie"

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.69
Adaptive Regularized Submodular Maximization

Authors: Shaojie Tang and Jing Yuan

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In this paper, we study the problem of maximizing the difference between an adaptive submodular (revenue) function and a non-negative modular (cost) function. The input of our problem is a set of n items, where each item has a particular state drawn from some known prior distribution The revenue function g is defined over items and states, and the cost function c is defined over items, i.e., each item has a fixed cost. The state of each item is unknown initially and one must select an item in order to observe its realized state. A policy π specifies which item to pick next based on the observations made so far. Denote by g_{avg}(π) the expected revenue of π and let c_{avg}(π) denote the expected cost of π. Our objective is to identify the best policy π^o ∈ arg max_π g_{avg}(π)-c_{avg}(π) under a k-cardinality constraint. Since our objective function can take on both negative and positive values, the existing results of submodular maximization may not be applicable. To overcome this challenge, we develop a series of effective solutions with performance guarantees. Let π^o denote the optimal policy. For the case when g is adaptive monotone and adaptive submodular, we develop an effective policy π^l such that g_{avg}(π^l) - c_{avg}(π^l) ≥ (1-1/e-ε)g_{avg}(π^o) - c_{avg}(π^o), using only O(nε^{-2}log ε^{-1}) value oracle queries. For the case when g is adaptive submodular, we present a randomized policy π^r such that g_{avg}(π^r) - c_{avg}(π^r) ≥ 1/eg_{avg}(π^o) - c_{avg}(π^o).
Cite as

Shaojie Tang and Jing Yuan. Adaptive Regularized Submodular Maximization. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 69:1-69:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{tang_et_al:LIPIcs.ISAAC.2021.69,
  author =	{Tang, Shaojie and Yuan, Jing},
  title =	{{Adaptive Regularized Submodular Maximization}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{69:1--69:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.69},
  URN =		{urn:nbn:de:0030-drops-155029},
  doi =		{10.4230/LIPIcs.ISAAC.2021.69},
  annote =	{Keywords: Adaptive submodularity, approximation algorithms, active learning}
}
  • Refine by Author
  • 1 Tang, Shaojie
  • 1 Yuan, Jing

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Submodular optimization and polymatroids
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 Adaptive submodularity
  • 1 active learning
  • 1 approximation algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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