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

Jun 8, 2026

Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

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.

Ishant Shanu

Submodular Optimization

Ask PDF

Jul 7, 2026

Data-dependent Evaluations for Budgeted Submodular Maximization

Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.

Lejian Zhang, Xueyan Tang, Jing Tang

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

Submodular Optimization Approximation Algorithms

Ask PDF

May 8, 2026

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight

63\%

approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend curvature -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for any submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime

1 \le c_g < 2.2

, the bound strictly beats the best known uniform ratio of

0.401

(for non-negative

f

), and it recovers the classical

(1-e^{-c_g})/c_g

guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.

Yixin Chen, Alan Kuhnle

Department of Computer Science & Engineering, Texas A&M University

Submodular Optimization Approximation Algorithms Greedy Optimization Curvature-Aware Optimization

Ask PDF

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