# Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

arXiv: https://arxiv.org/abs/2606.14764 · HTML: https://mlsanity.com/paper/2606.14764/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 8 Jun 2026.

## Builds on (most cited first, 7 of 7)

- [Encoder-Decoder with Atrous Separable Convolution for Semantic Image Segmentation](https://mlsanity.com/paper/1802.02611/) (2018)
- [A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems](https://mlsanity.com/paper/1404.0533/) (2014)
- [Reflection methods for user-friendly submodular optimization](https://mlsanity.com/paper/1311.4296/) (2013)
- [Near-optimal Approximate Discrete and Continuous Submodular Function Minimization](https://mlsanity.com/paper/1909.00171/) (2019)
- [Provable Submodular Minimization using Wolfe's Algorithm](https://mlsanity.com/paper/1411.0095/) (2014)
- [Subquadratic Submodular Function Minimization](https://mlsanity.com/paper/1610.09800/) (2016)
- [Dualization in Lattices Given by Ordered Sets of Irreducibles](https://mlsanity.com/paper/1504.01145/) (2015)

## Abstract (arXiv)

Submodular function minimization has gained a lot of interest in recent years. They are highly applicable in the area of Computer Vision and Machine Learning. Often such applications require to work with submodular functions defined on distributive lattice. Current best way of dealing with it is using a transformation which extrapolates the submodular function for the respective boolean lattice. It makes optimization system too inefficient due to enlargement of the working space. Quantitatively, the expanded space has additional exponential (in set size) number of elements. We propose a generic framework for dealing with distributive lattice which only works within distributive lattice. Our framework allows one to use already established submodular function minimization algorithms for boolean lattice. In our experiment, we show the huge improvement in terms of running time over tranditional methods for handling distributive lattice.