Submodular functions, maximizing



Submodular functions arise in economics of multi-agent games and in various discrete optimization problems that look like problems facing me, but not so much that I actually have anything useful to say here. I am mostly making this note so I remember the connection with implicit layers via convex relaxations.

References

Balkanski, Eric, and Yaron Singer. 2018a. “Approximation Guarantees for Adaptive Sampling,” 17. https://scholar.harvard.edu/files/ericbalkanski/files/approximation-guarantees-for-adaptive-sampling.pdf.
———. 2018b. “The Adaptive Complexity of Maximizing a Submodular Function,” 37. https://scholar.harvard.edu/files/ericbalkanski/files/the-adaptive-complexity-of-maximizing-a-submodular-function.pdf.
Djolonga, Josip, and Andreas Krause. 2017. “Differentiable Learning of Submodular Models.” In Proceedings of the 31st International Conference on Neural Information Processing Systems, 1014–24. NIPS’17. Red Hook, NY, USA: Curran Associates Inc. https://proceedings.neurips.cc/paper/2017/file/192fc044e74dffea144f9ac5dc9f3395-Paper.pdf.
Krause, Andreas, and Daniel Golovin. 2013. “Submodular Function Maximization.” In Tractability, edited by Lucas Bordeaux, Youssef Hamadi, Pushmeet Kohli, and Robert Mateescu, 71–104. Cambridge: Cambridge University Press. https://doi.org/10.1017/CBO9781139177801.004.
Lovász, L. 1983. “Submodular Functions and Convexity.” In Mathematical Programming The State of the Art: Bonn 1982, edited by Achim Bachem, Bernhard Korte, and Martin Grötschel, 235–57. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-68874-4_10.
Toriello, Alejandro. n.d. “A Brief Lecture on Submodular Functions,” 8.
Tschiatschek, Sebastian, Aytunc Sahin, and Andreas Krause. 2018. “Differentiable Submodular Maximization.” In Proceedings of the 27th International Joint Conference on Artificial Intelligence, 2731–38. IJCAI’18. Stockholm, Sweden: AAAI Press. http://arxiv.org/abs/1803.01785.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.