Supermodular Rank: Set Function Decomposition and Optimization

Rishi Sonthalia; Anna Seigal; Guido Montufar

math.COMay 24, 2023

Supermodular Rank: Set Function Decomposition and Optimization

Authors: Rishi Sonthalia, Anna Seigal, Guido Montufar

Organizations: UCLA · Harvard University · UCLA and MPI MiS

Abstract

We define the supermodular rank of a function on a lattice. This is the smallest number of terms needed to decompose it into a sum of supermodular functions. The supermodular summands are defined with respect to different partial orders. We characterize the maximum possible value of the supermodular rank and describe the functions with fixed supermodular rank. We analogously define the submodular rank. We use submodular decompositions to optimize set functions. Given a bound on the submodular rank of a set function, we formulate an algorithm that splits an optimization problem into submodular subproblems. We show that this method improves the approximation ratio guarantees of several algorithms for monotone set function maximization and ratio of set functions minimization, at a computation overhead that depends on the submodular rank.

Figures & tables

Submodular
$n$	rank 1	rank 2	rank 3	rank 4
3	12.5%	74.9%	100%	-
4	0.0072%	5.9%	100%	-
Elementary Submodular
$n$	rank 1	rank 2	rank 3	rank 4
3	3.14%	53.16%	100%	-

Table 1: Volume estimates.

Panel of Table 2 — Table 2: Approximation ratios and time complexity for maximizing a monotone, normalized function $f$ on $2^{[n]}$ of total curvature $\hat{\alpha}$ , generalized curvature $\alpha$ , submodularity ratio $\gamma$ , and elementary submodular rank $r+1$ . Here, $m$ is the bound in the cardinality constraint, and $\rho$ is the matroid rank in the matroid constraint. Results with ∗ are in expectation over randomization in the algorithm. The check marks indicate requirements on $f$ or the problem setting.

	Numerator	Denominator	Approx. Ratio	Time	Ref.
Prior Work	Modular	Modular	1	$O(n^{2})$	Thm 54 [ 4 ]
	Modular	Submodular	$1-e^{-1}$	$O(n^{2})$	Thm 54 [ 4 ]
	Submodular	Submodular	$\frac{1}{1-e^{\hat{\alpha}^{f}-1}}$	$O(n^{2})$	Thm 54 [ 4 ]
	Submodular	-	$\frac{1}{\gamma_{\emptyset,\|X^{}\|}^{g}}\frac{\|X^{}\|}{1+(\|X^{}\|-1)(1-\hat{c}^{f}(X^{}))}$	$O(n^{2})$	Thm 56 [ 39 ]
	-	-	$\frac{1}{\gamma^{g}_{\emptyset,\|X^{}\|}}\frac{\|X^{}\|}{1+(\|X^{*}\|-1)(1-\alpha^{f})(1-\tilde{\alpha}^{f})}$	$O(n^{2})$	Thm 57 [ 49 ]
This Work	Low Rank	-	$\frac{1}{\gamma_{\emptyset,\|X^{}\|}^{g}}\frac{\|X^{}\|}{1+(\|X^{}\|-1)(1-\hat{c}^{f}(X^{}))}$	$O(2^{r_{f}}n^{r_{f}}\cdot n^{2})$	Thm 58

Table 3: Approximation ratios and time complexity for minimizing

f/g

for monotone, normalized functions

f

and

g

2^{[n]}

. Here

f

has total curvature

\hat{\alpha}^{f}

, generalized curvature

\alpha^{f}

, generalized inverse curvature

\tilde{\alpha}^{f}

, curvature

\hat{c}^{f}

, and elementary submodular rank

r_{f}+1

g

has submodularity ratio

\gamma^{g}

and elementary submodular rank

r_{g}+1

X^{*}

is the optimal solution.

Panel of Figure 2 — Figure 2: Shown are (a) how the bound from [ 5 ] changes when we use $\alpha_{r}$ and $\gamma_{r}$ (see Definition 43 ); higher values correspond to better guarantees, (b) the relative error when approximating a function by an elementary rank- $(r+1)$ function, and (c) the running times for computing the approximation.

Panel of Figure 3 — Figure 3: Shown are (a) the approximation ratio for the solution found versus the optimal solution averaged over 50 objective functions in each type, (b) the proportion of instances for which the algorithms find the optimal solution, (c) the ratio of the solution found by 1 Split and Greedy .

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

() $[n]$	$\{1,\ldots,n\}$ .
() $(X,\pi)$	A poset $X$ with partial order defined by a tuple $\pi$ .
() $f$	A function from a poset $(X,\pi)$ to $\mathbb{R}$ .
() $\mathcal{L_{\pi}}$	The cone of $\pi$ -supermodular functions.
() $\pi$	Tuple of $n$ linear orders $\pi=(\pi_{1},\ldots,\pi_{n})$ , see Definition 5 .
() $A^{(ij)}$	The $(ij)$ elementary imset matrix, a $2^{n-2}\times 2^{n}$ matrix that collects the imset inequalities for each $x\in\{0,1\}^{n-2}$ , see Definition 7 .
() $\tau$	Sign vector $\tau=(\tau_{1},\ldots,\tau_{n})$ of a tuple of linear orders $\pi$ , see Definition 9 .

Appendix

Table 4: Notation used in the paper

Submodular Optimization

Submodular optimization studies efficient selection and allocation when each added item tends to provide diminishing returns.

See all 52 papers

Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization
Jun 8, 2026Ishant ShanuSubmodular Optimization
Data-dependent Evaluations for Budgeted Submodular Maximization
Jul 7, 2026Lejian Zhang, Xueyan Tang, Jing TangSubmodular Optimization Approximation Algorithms
College of Computing and Data Science, Nanyang Technological University, Singapore · Data Science and Analytics Thrust, The Hong Kong University of Science and Technology (Guangzhou), China
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
May 8, 2026Yixin Chen, Alan KuhnleSubmodular Optimization Approximation Algorithms
Department of Computer Science & Engineering, Texas A&M University

Jun 8, 2026J/K move · Enter open · S save

Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

Ishant Shanu

Submodular Optimization

Open paper AskPDF 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.

Abstract

Submodular Optimization

Explore similar work

Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

Data-dependent Evaluations for Budgeted Submodular Maximization

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions