Document Open Access Logo

Multi-Agent Submodular Optimization

Authors Richard Santiago, F. Bruce Shepherd

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2018.23.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Submodular optimization and polymatroids
Keywords
  • submodular optimization
  • multi-agent
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.23

Author Details

Richard Santiago
  • McGill University, Montreal, Canada
F. Bruce Shepherd
  • University of British Columbia, Vancouver, Canada

References

  1. Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a non-symmetric technique. arXiv preprint arXiv:1611.03253, 2016. Google Scholar
  2. Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz. A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM Journal on Computing, 44(5):1384-1402, 2015. Google Scholar
  3. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. In Integer programming and combinatorial optimization, pages 182-196. Springer, 2007. Google Scholar
  4. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740-1766, 2011. Google Scholar
  5. Chandra Chekuri and Alina Ene. Submodular cost allocation problem and applications. In International Colloquium on Automata, Languages, and Programming, pages 354-366. Springer, 2011. Extended version: arXiv preprint arXiv:1105.2040. Google Scholar
  6. Alina Ene and Huy L Nguyen. Constrained submodular maximization: Beyond 1/e. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 248-257. IEEE, 2016. Google Scholar
  7. Alina Ene and Jan Vondrák. Hardness of submodular cost allocation: Lattice matching and a simplex coloring conjecture. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), 28:144-159, 2014. Google Scholar
  8. Uriel Feige, Vahab S Mirrokni, and Jan Vondrak. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133-1153, 2011. Google Scholar
  9. Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 570-579. IEEE, 2011. Google Scholar
  10. Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey. An analysis of approximations for maximizing submodular set functions-II. Springer, 1978. Google Scholar
  11. Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum general assignment problems. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 611-620. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  12. Gagan Goel, Chinmay Karande, Pushkar Tripathi, and Lei Wang. Approximability of combinatorial problems with multi-agent submodular cost functions. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 755-764. IEEE, 2009. Google Scholar
  13. Michel X. Goemans and VS Ramakrishnan. Minimizing submodular functions over families of sets. Combinatorica, 15(4):499-513, 1995. Google Scholar
  14. Pranava R Goundan and Andreas S Schulz. Revisiting the greedy approach to submodular set function maximization. Optimization online, pages 1-25, 2007. Google Scholar
  15. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science &Business Media, 2012. Google Scholar
  16. Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In International Workshop on Internet and Network Economics, pages 246-257. Springer, 2010. Google Scholar
  17. Ara Hayrapetyan, Chaitanya Swamy, and Éva Tardos. Network design for information networks. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 933-942. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  18. Elad Hazan, Shmuel Safra, and Oded Schwartz. On the complexity of approximating k-set packing. computational complexity, 15(1):20-39, 2006. Google Scholar
  19. Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM (JACM), 48(4):761-777, 2001. Google Scholar
  20. Satoru Iwata and Kiyohito Nagano. Submodular function minimization under covering constraints. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 671-680. IEEE, 2009. Google Scholar
  21. Rishabh Iyer, Stefanie Jegelka, and Jeff Bilmes. Monotone closure of relaxed constraints in submodular optimization: Connections between minimization and maximization: Extended version, 2014. Google Scholar
  22. Subhash Khot, Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. In International Workshop on Internet and Network Economics, pages 92-101. Springer, 2005. Google Scholar
  23. Christos Koufogiannakis and Neal E Young. Greedy δ-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica, 66(1):113-152, 2013. Google Scholar
  24. Andreas Krause and Carlos Guestrin. Near-optimal observation selection using submodular functions. In AAAI, volume 7, pages 1650-1654, 2007. Google Scholar
  25. Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos. Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources Planning and Management, 134(6):516-526, November 2008. Google Scholar
  26. KW Krause, MA Goodwin, and RW Smith. Optimal software test planning through automated network analysis. TRW Systems Group, 1973. Google Scholar
  27. Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 323-332. ACM, 2009. Google Scholar
  28. Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple matroids via generalized exchange properties. Mathematics of Operations Research, 35(4):795-806, 2010. Google Scholar
  29. Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-296, 2006. URL: http://EconPapers.repec.org/RePEc:eee:gamebe:v:55:y:2006:i:2:p:270-296.
  30. László Lovász. Submodular functions and convexity. In Mathematical Programming The State of the Art, pages 235-257. Springer, 1983. Google Scholar
  31. Vahab Mirrokni, Michael Schapira, and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the 9th ACM conference on Electronic commerce, pages 70-77. ACM, 2008. Google Scholar
  32. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions - i. Mathematical Programming, 14(1):265-294, 1978. Google Scholar
  33. George L Nemhauser and Leonard A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177-188, 1978. Google Scholar
  34. Richard Santiago and F Bruce Shepherd. Multivariate submodular optimization. arXiv preprint arXiv:1612.05222, 2016. Google Scholar
  35. Richard Santiago and F Bruce Shepherd. Multi-agent submodular optimization. arXiv preprint arXiv:1803.03767, 2018. Google Scholar
  36. Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80(2):346-355, 2000. Google Scholar
  37. Ajit Singh, Andrew Guillory, and Jeff Bilmes. On bisubmodular maximization. In Artificial Intelligence and Statistics, pages 1055-1063, 2012. Google Scholar
  38. Zoya Svitkina and Lisa Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM Journal on Computing, 40(6):1715-1737, 2011. Google Scholar
  39. Zoya Svitkina and ÉVA Tardos. Facility location with hierarchical facility costs. ACM Transactions on Algorithms (TALG), 6(2):37, 2010. Google Scholar
  40. Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67-74. ACM, 2008. Google Scholar
  41. Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265-304, 2013. Google Scholar
  42. Jan Vondrák, Chandra Chekuri, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 783-792. ACM, 2011. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact