Topkis, D. M. (1978). Minimizing a submodular function on a lattice. Operations research, 26(2), 305-321. PDF
This paper is a theoretical study of the problem of minimizing submodular functions, including
- for a set of optimization problems with parameter-dependent objective functions and constraints, it gives general conditions for the optimal solution to be a monotonically increasing function of the parameters.
- explore and elaborate the theory of minimization problems on the lattice of submodular functions.
- introduce a natural semi-ordered relation on the set of non-empty sublattices of a lattice and show its properties.
- clarifies the relationship between submodularity and anti-tone difference and shows the operations that generate and preserve submodular functions.
- the problem of minimizing a submodular function, giving conditions for the optimal solution set to be a sublattice and to have a maximum and minimum source.
- the conditions under which a submodular function defined on a sublattice of a lattice can be extended to a submodular function on the whole lattice.
- derives sufficient conditions for the optimal solution set to be monotonically increasing with respect to parameters and for the existence of monotonically increasing optimal solutions.
- also notes the similarities between submodular functions and convex functions.
The potential for application in various fields is pointed out, and the paper contains important theoretical and applied content, with examples of applications to network flows, game theory, inventory theory, mathematical programming, and other areas shown in subsequent papers.
This page is auto-translated from [/nishio/Minimizing a Submodular Function on a Lattice](https://scrapbox.io/nishio/Minimizing a Submodular Function on a Lattice) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.