License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.23
URN: urn:nbn:de:0030-drops-94276
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9427/
Santiago, Richard ;
Shepherd, F. Bruce
Multi-Agent Submodular Optimization
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.
BibTeX - Entry
@InProceedings{santiago_et_al:LIPIcs:2018:9427,
author = {Richard Santiago and F. Bruce Shepherd},
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 = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9427},
URN = {urn:nbn:de:0030-drops-94276},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.23},
annote = {Keywords: submodular optimization, multi-agent, approximation algorithms}
}
|
Keywords: |
|
submodular optimization, multi-agent, approximation algorithms |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
13.08.2018 |
