2 Search Results for "Santiago, Richard"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.64
Weakly Submodular Function Maximization Using Local Submodularity Ratio

Authors: Richard Santiago and Yuichi Yoshida

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) functions that arise in practice can be efficiently maximized with provable guarantees. In this work we introduce two natural generalizations of weak submodularity for non-monotone functions. We show that an efficient randomized greedy algorithm has provable approximation guarantees for maximizing these functions subject to a cardinality constraint. We then provide a more refined analysis that takes into account that the weak submodularity parameter may change (sometimes improving) throughout the execution of the algorithm. This leads to improved approximation guarantees in some settings. We provide applications of our results for monotone and non-monotone maximization problems.
Cite as

Richard Santiago and Yuichi Yoshida. Weakly Submodular Function Maximization Using Local Submodularity Ratio. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{santiago_et_al:LIPIcs.ISAAC.2020.64,
  author =	{Santiago, Richard and Yoshida, Yuichi},
  title =	{{Weakly Submodular Function Maximization Using Local Submodularity Ratio}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{64:1--64:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.64},
  URN =		{urn:nbn:de:0030-drops-134082},
  doi =		{10.4230/LIPIcs.ISAAC.2020.64},
  annote =	{Keywords: weakly submodular, non-monotone, local submodularity ratio}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.23
Multi-Agent Submodular Optimization

Authors: Richard Santiago and F. Bruce Shepherd

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

Abstract
Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) min/max~f(S): S in F, where F is a given family of feasible sets over a ground set V and f:2^V - > R is submodular. This progress has been coupled with a wealth of new applications for these models. Our focus is on a more general class of multi-agent submodular optimization (MASO) min/max Sum_{i=1}^{k} f_i(S_i): S_1 u+ S_2 u+ ... u+ S_k in F. Here we use u+ to denote disjoint union and hence this model is attractive where resources are being allocated across k agents, each with its own submodular cost function f_i(). This was introduced in the minimization setting by Goel et al. In this paper we explore the extent to which the approximability of the multi-agent problems are linked to their single-agent versions, referred to informally as the multi-agent gap. We present different reductions that transform a multi-agent problem into a single-agent one. For minimization, we show that (MASO) has an O(alpha * min{k, log^2 (n)})-approximation whenever (SO) admits an alpha-approximation over the convex formulation. In addition, we discuss the class of "bounded blocker" families where there is a provably tight O(log n) multi-agent gap between (MASO) and (SO). For maximization, we show that monotone (resp. nonmonotone) (MASO) admits an alpha (1-1/e) (resp. alpha * 0.385) approximation whenever monotone (resp. nonmonotone) (SO) admits an alpha-approximation over the multilinear formulation; and the 1-1/e multi-agent gap for monotone objectives is tight. We also discuss several families (such as spanning trees, matroids, and p-systems) that have an (optimal) multi-agent gap of 1. These results substantially expand the family of tractable models for submodular maximization.
Cite as

Richard Santiago and F. Bruce Shepherd. Multi-Agent Submodular Optimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{santiago_et_al:LIPIcs.APPROX-RANDOM.2018.23,
  author =	{Santiago, Richard and Shepherd, F. Bruce},
  title =	{{Multi-Agent Submodular Optimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.23},
  URN =		{urn:nbn:de:0030-drops-94276},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.23},
  annote =	{Keywords: submodular optimization, multi-agent, approximation algorithms}
}
  • Refine by Author
  • 2 Santiago, Richard
  • 1 Shepherd, F. Bruce
  • 1 Yoshida, Yuichi

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

  • Refine by Keyword
  • 1 approximation algorithms
  • 1 local submodularity ratio
  • 1 multi-agent
  • 1 non-monotone
  • 1 submodular optimization
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020

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