Source-linked AI summary
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
Rishabh Iyer, Jeff Bilmes
TL;DR
The paper studies minimizing a monotone submodular cost under a submodular cover constraint and maximizing submodular utility under a submodular knapsack constraint, motivated by applications such as sensor placement and data subset selection. It develops surrogate-based approximation algorithms, relates the two problems through bicriterion transformations, and reports bounded guarantees with empirical scalability. The analysis also identifies costly algorithms and leaves broader real-world evaluation as future work.
Problem
The paper addresses constrained optimization of submodular cost and utility functions because difference-of-submodular formulations are worst-case inapproximable.
Method
The paper uses surrogate functions, including modular bounds and approximations, within a unified iterative framework and transforms bicriterion algorithms between SCSC and SCSK.
Results
The transformations provide [(1 − ϵ)ρ, σ] and [(1 + ϵ)σ, ρ] guarantees, while EASSC obtains O(√n log n) approximation and greedy SCSK has a curvature-dependent factor.
Takeaways & Limitations
The framework unifies approximation algorithms for both constrained problems and supports practical iterative methods alongside tighter but more intensive algorithms.
Takeaways & Limitations
EASSC and EASK are enormously costly and complicated, and broader evaluation on several real-world applications remains future work.
Abstract
from arXiv · showhide
We investigate two new optimization problems -- minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound constraint (submodular knapsack). We are motivated by a number of real-world applications in machine learning including sensor placement and data subset selection, which require maximizing a certain submodular function (like coverage or diversity) while simultaneously minimizing another (like cooperative cost). These problems are often posed as minimizing the difference between submodular functions [14, 35] which is in the worst case inapproximable. We show, however, that by phrasing these problems as constrained optimization, which is more natural for many applications, we achieve a number of bounded approximation guarantees. We also show that both these problems are closely related and an approximation algorithm solving one can be used to obtain an approximation guarantee for the other. We provide hardness results for both problems thus showing that our approximation factors are tight up to log-factors. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.
1 Introduction
The paper introduces SCSC and SCSK, constrained formulations for jointly optimizing monotone submodular cost and utility functions in applications such as sensor placement and data subset selection. It develops approximation guarantees and connects these problems to existing optimization tasks and to each other.
- Problem formulation: SCSC minimizes f(X) subject to g(X) ≥ c, while SCSK maximizes g(X) subject to f(X) ≤ b.Here f and g are normalized, monotone non-decreasing submodular functions; c and b are cover and budget parameters.
- Motivation: 13 The unconstrained difference-of-submodular formulation is worst-case NP-hard and inapproximable, even when both functions are monotone.Exact branch-and-bound methods can also have exponential worst-case complexity.
- Motivation: The formulations capture applications requiring high submodular utility together with low cooperative submodular cost, including sensor placement and data subset selection.Sensor costs may exhibit bulk discounts and location-dependent reuse, while vocabulary selection balances coverage against vocabulary size.
- Connections: Problems 1 and 2 subsume Set Cover, Max k-Cover, knapsack, and several constrained submodular optimization problems.Special cases arise when one or both functions are modular, or when a submodular function supplies a matroid-span constraint.
- Contributions: The paper provides a unified approximation framework, establishes near-tight hardness results, and reports that iterative algorithms often outperform their worst-case guarantees empirically.The framework connects the two problems, yields curvature-dependent guarantees, and includes algorithms designed for practical scalability.
2 Background and Main Ideas
The algorithmic framework replaces difficult submodular objectives or constraints with suitable modular bounds and other surrogate functions, often optimized iteratively. Curvature measures departure from modularity and sharpens the resulting approximation analysis.
- Framework: Algorithm 1 iteratively chooses surrogate functions tight at the current solution and optimizes the corresponding surrogate version of SCSC or SCSK.Surrogates may be upper or lower bounds, or other approximations, chosen to make each subproblem easier.
- Modular bounds: Subgradients provide modular lower bounds tight at a reference set, while supergradients define modular upper bounds for submodular functions.These bounds support majorization-minimization updates for the constrained problems.
- MM algorithms: Choosing a modular upper bound for f, a modular lower bound for g, or both, ensures objective improvement in the MM framework.The bounds are selected to remain tight at the current iterate.
- Curvature-aware approximation: Curve normalization separates the zero-curvature component from the polymatroidal component, allowing approximation of only the latter while retaining the linear part exactly.Ellipsoidal approximations can then be used as surrogate functions whose multiplicative bounds yield guarantees for SCSC and SCSK.
3 Relation between SCSC and SCSK
SCSC and SCSK are polynomially transformable into one another through bicriterion algorithms, so an approximation method for either problem yields guarantees for the other. Binary search reduces transformation calls relative to linear search, with exact bicriterion factors for integral functions.
- Relationship: The paper establishes that SCSC and SCSK are dual problems that are polynomially transformable into each other.Thus, an approximation algorithm for one problem can provide an approximation guarantee for the other.
- Bicriterion guarantees: A [σ, ρ] bicriterion algorithm permits σ-factor approximate optimality and ρ-factor approximate feasibility, with the roles reversed for the dual problem.Typically σ ≥ 1 and ρ ≤ 1.
- Linear-search transformation: Theorem 3.1 gives a [(1 − ϵ)ρ, σ] SCSK approximation after at most log1/(1−ϵ)[g(V) / min_j g(j)] SCSC calls, with a symmetric result for SCSC.The reverse transformation uses log1+ϵ[f(V) / min_j f(j)] SCSK calls.
- Binary-search transformation: Binary search requires at most log2 1/ϵ calls for the corresponding transformed approximation guarantees.For integral f and g, the dependence on ϵ disappears and the number of iterations becomes log2 g(V).
- Integral case: For integral functions, the binary-search transformation obtains exact [ρ, σ] or [σ, ρ] bicriterion guarantees and can potentially be faster in practice.The paper also notes that direct algorithms for polymatroid functions can be faster than iterative reductions.
4 Approximation Algorithms
The paper develops approximation algorithms for submodular cover and knapsack problems by replacing difficult functions with suitable modular or ellipsoidal surrogates. The resulting methods include practical iterative algorithms, tighter but costly ellipsoidal variants, and extensions to more complex constraints.
- Submodular Set Cover: The primal greedy algorithm for submodular set cover achieves an Hg approximation, while the dual approach gives a [1 + ϵ, 1 −e^-1] bicriterion guarantee.Hg is defined as H(maxj g(j)); the greedy factor is tight up to lower-order terms.
- Submodular Set Cover: The primal ISSC algorithm obtains KgHg / [1+(Kg−1)(1−κf)] approximation, with Kg ≤ n and curvature κf improving the guarantee when cost is less curved.When f is modular, κf = 0 and the guarantee recovers the submodular set cover bound; additional iterations can only improve the objective.
- Submodular Set Cover: The primal EASSC guarantee is O(√n log n Hg / [1+(√n log n−1)(1−κf)]), while its dual gives [O(√n log n), 1 −e^-1].The analysis derives this from ellipsoidal approximations and the submodular set cover guarantee.
- Submodular Knapsack: For submodular knapsack, greedy and iterative methods provide practical guarantees, including (1 −e^-1) for ISK and a type-I bicriterion factor [1 −e^-1, Kf / [1+(Kf−1)(1−κf)]].The first-iteration bound already holds, and subsequent ascent iterations improve the objective.
- Submodular Knapsack: Ellipsoidal EASK obtains a [1 −e^-1, O(√n log n)] bicriterion guarantee in the κf = 1 case, but EASK and EASSC are enormously costly and complicated.The ellipsoidal approximation can be computed once and reused across conversion rounds.
- Extensions: The algorithms extend to multiple ‘or’ constraints and other more complicated submodular constraint functions.The paper gives a recursive construction for multiple ‘or’ constraints and describes corresponding SCSK extensions.
5 Experiments
The experiments evaluate the proposed algorithms on speech data subset selection, modeling vocabulary coverage and acoustic variability with submodular objectives. Iterative methods perform competitively with more intensive approximation methods and substantially outperform random selection.
- Experimental setup: Speech subset selection balances limited vocabulary through f(X)=|Γ(X)| against acoustic variability through coverage function g.The experiments use facility location and saturated sum functions for coverage.
- Experimental setup: The experiments use a TIMIT similarity matrix built with the string kernel metric and restrict instances to 50 utterances.The restriction reflects the computational intensity of Ellipsoidal Approximation methods.
- Results: Iterative algorithms Gr, ISSC, and ISK perform comparably to the more complicated EA-based algorithms, despite the latter having better theoretical guarantees.The neighborhood function has curvature κ_f=1, motivating simpler EASSC_c and EASK_c variants.
- Results: All proposed algorithms perform much better than random sets of varying cardinality on the real-world instances.
6 Discussions and related work
The paper presents a unified approximation framework for submodular cover and knapsack problems, combining transferable guarantees with practical iterative algorithms and tighter-bound alternatives. It also emphasizes that preserving hard constraint guarantees matters in applications, while identifying limits on broader extensions.
- Contributions: The framework uses surrogate functions and iterative algorithms based on efficiently solvable subproblems formed from upper or lower bounds.
- Contributions: Iterative algorithms are practical and scalable, while EASSC and EASK obtain tight approximation bounds at greater computational intensity.
- Discussion and limitations: Casting applications as an unconstrained difference-of-submodular problem removes guarantees on deviation from hard power or budget constraints.