Submodular functions, maximising

July 9, 2018 — July 9, 2018

complexity
compsci
optimization

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

Figure 1

1 References

Balkanski, and Singer. 2018a. “Approximation Guarantees for Adaptive Sampling.”
———. 2018b. “The Adaptive Complexity of Maximizing a Submodular Function.”
Djolonga, and Krause. 2017. “Differentiable Learning of Submodular Models.” In Proceedings of the 31st International Conference on Neural Information Processing Systems. NIPS’17.
Krause, and Golovin. 2013. “Submodular Function Maximization.” In Tractability.
Lovász. 1983. “Submodular Functions and Convexity.” In Mathematical Programming The State of the Art: Bonn 1982.
Toriello. n.d. “A Brief Lecture on Submodular Functions.”
Tschiatschek, Sahin, and Krause. 2018. “Differentiable Submodular Maximization.” In Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI’18.