Source-linked AI summary
Submodular approximation: sampling-based algorithms and lower bounds
Zoya Svitkina, Lisa Fleischer
TL;DR
The paper asks how well several classical optimization and submodular-function learning problems can be solved or approximated when objectives are general submodular functions using polynomially many value-oracle queries. It develops randomized sampling-based algorithms and proves upper and lower bounds, showing that most approximation guarantees are on the order of sqrt(n/ln n) and that constant or polylogarithmic approximations are impossible in this model.
Problem
The paper studies generalizations of classical optimization problems and the difficulty of approximating or learning general submodular functions with polynomially many value-oracle queries.
Method
The paper develops randomized algorithms that sample subsets and use submodular minimization, alongside oracle-indistinguishability lower-bound constructions and structured-function analyses.
Results
Most algorithms achieve approximation guarantees on the order of sqrt(n/ln n), while matching or nearly matching lower bounds rule out constant or polylogarithmic approximations for the studied problems.
Takeaways & Limitations
Improving these guarantees for specific applications requires restricting the model or the class of submodular functions rather than allowing arbitrary oracle-accessible functions.
Takeaways & Limitations
The lower bounds apply in the value-oracle model and indicate that arbitrary submodular functions prevent constant or polylogarithmic approximations.
Abstract
from arXiv · showhide
We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees for most of our algorithms are of the order of sqrt(n/ln n). We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem of approximately learning a monotone submodular function. In addition, we present an algorithm for approximately learning submodular functions with special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. This demonstrates that if there are significantly stronger lower bounds for this problem, they rely on more general submodular functions.
1 Introduction
The paper studies classical optimization problems whose objectives are replaced by general submodular functions, and establishes approximation algorithms and lower bounds in the value-oracle model. Most guarantees are on the order of sqrt(n/ln n), with lower bounds showing this difficulty is inherent.
- Background: Submodular functions generalize graph cut and matrix or matroid rank functions and model decreasing marginal returns in applications such as scheduling and network design.
- New problems: The paper introduces submodular load balancing, sparsest cut, balanced cut, and function minimization with a cardinality lower bound.These problems replace simpler objectives from load balancing, graph cuts, and minimum knapsack with submodular functions.
- Results: sqrt(n/ln n) approximations are proved for most algorithms, contrasting with constant or logarithmic guarantees for corresponding classical problems.
- Results and techniques: Randomized algorithms sample subsets, seek samples overlapping substantially with an optimal set, and use submodular minimization to construct candidate solutions.
- Results and techniques: Matching or nearly matching lower bounds rule out constant and polylogarithmic approximations for the studied problems using polynomially many value-oracle queries.
- Results and techniques: For SML, the paper also studies bicriteria guarantees that trade objective quality against the required cardinality or weight.A (ρ, σ)-approximation permits cost at most ρB and weight at least σW when a feasible benchmark set exists.
2 Preliminaries
The preliminaries establish how the paper’s randomized decision procedures operate and how oracle indistinguishability yields lower bounds. They also introduce the sampling probability tools used in algorithm analyses.
- Basic tools: Polynomial-time submodular minimization applies because sums of submodular functions remain submodular.This supports minimizing expressions such as f(T) − α · |T ∩ S|.
- Decision procedures: A randomized relaxed decision procedure either declares infeasibility or returns a solution with objective value at most γB.The procedure is given a minimization instance, target B, and probability p.
- Lower bounds: Oracle indistinguishability implies that polynomially many queries distinguish two functions only with probability n^-ω(1) when any fixed query separates them with that probability.
- Lower bounds: The lower-bound argument follows a fixed computation path for deterministic algorithms and extends to randomized algorithms by viewing them as distributions over deterministic ones.
- Random sampling: The sampling theorem bounds the probability of selecting exactly ⌈qm(1 + ε)⌉ elements when each of m elements is sampled independently with probability q.
3 Submodular sparsest cut and submodular balanced cut
This section develops submodular sparsest-cut and balanced-cut algorithms and matching oracle-model lower bounds, including for symmetric functions. The results use randomized sampling and show that polynomial-query algorithms face substantial approximation barriers.
- 3.1 Lower bounds: The hard instances use nonnegative, submodular, symmetric functions whose oracle values differ with probability at most n^-ω(1) on any fixed queried set.This indistinguishability result prevents polynomial-query algorithms from reliably identifying which function they receive.
- 3.1 Lower bounds: Polynomial-query algorithms cannot approximate uniform submodular sparsest cut or unweighted submodular balanced cut to ratio o(sqrt(n/ln n)), even for symmetric functions.The lower bounds rely on functions that are hard to distinguish through polynomially many value-oracle queries.
- 3.2 Submodular sparsest cut: The sparsest-cut algorithm assigns signed demand weights using a random node set, then minimizes a submodular objective biased toward separating demand pairs crossing that set.Separated pairs contribute positive weight to the node inside the random set and negative weight to the node outside it.
- 3.2 Submodular sparsest cut: For every feasible submodular sparsest-cut instance, Algorithm 1 returns a solution of cost at most 4sqrt(n/ln n)·B with probability at least p.The guarantee is stated for an instance with a feasible solution of benchmark cost B.
- 3.3 Submodular balanced cut: For symmetric functions, Algorithm 2 repeatedly collects smaller sides of approximate sparsest cuts until the accumulated set becomes b′-balanced.The procedure sets corresponding element weights to zero rather than removing graph parts, so the collected sets need not be disjoint.
- 3.3 Submodular balanced cut: A second balanced-cut algorithm extends the approach to arbitrary nonnegative submodular functions and produces a b′/2-balanced cut with an O(·) cost guarantee.The supplied theorem passage gives the balance form but truncates the displayed cost expression.
4 Submodular minimization with cardinality lower bound
This section studies minimizing a submodular function subject to a cardinality or weight lower bound. It proves oracle lower bounds and gives a randomized bicriteria decision procedure for the weighted problem.
- 4.1 Lower bounds: Polynomial-query algorithms cannot distinguish the monotone submodular functions f3 and f4 with probability greater than n^-ω(1).The construction chooses a random subset R and uses concentration bounds to make oracle answers nearly identical on queried sets.
- 4.1 Lower bounds: There is no (ρ,σ)-bicriteria approximation algorithm for SML for the parameter range stated in Theorem 4.2, even with monotone functions.The proof constructs instances where an algorithm’s output would distinguish f3 from f4.
- 4.2 Algorithm for SML: Algorithm 4 builds a feasible SML solution by repeatedly adding sets obtained from submodular function minimization.Its two cases depend on whether the target weight W is at least or less than half the total weight.
- 4.2 Algorithm for SML: The resulting output satisfies f(U)≤5sqrt(ln n)B and w(U)≥W/2 with probability at least p.The guarantee is for feasible instances and is established by combining the final iteration’s function-value bound with the loop exit condition.
- 4.2 Algorithm for SML: The algorithm’s randomized second case samples elements into Si and minimizes f(T)−α·w(T∩Si) to find a useful nonempty augmentation.The analysis shows that suitable inequalities make the minimizer satisfy the algorithm’s addition conditions.
5 Submodular load balancing
The paper develops sampling-based algorithms and oracle-query lower bounds for submodular load balancing, showing that polynomial-query algorithms face near-matching approximation barriers.
- 5.1 Lower bound: The lower-bound construction uses m = 5√ and parameters satisfying x^2 = ω(ln n).The hidden partition consists of random equal-sized sets, and α and β are chosen to be integers.
- 5.1 Lower bound: Polynomial-query algorithms cannot distinguish two submodular functions whose optimal SLB values differ by a large factor.The indistinguishability probability is n−ω(1), yielding an unconditional oracle-model lower bound.
- 5.1 Lower bound: A random hidden partition makes the two hard functions agree on queried sets with probability n−ω(1).The distinguishing argument reduces to bounding the chance that some queried set intersects a hidden block in more than β elements.
- Algorithms: Two randomized algorithms are given for uniform SLB, improving from a simple equal-size partitioning method to a more complex sampling algorithm.The complex algorithm samples small low-ratio sets, groups them, and completes the partition with residual elements.
- Algorithms: The algorithms’ guarantees match or nearly match the lower bound for the uniform SLB problem.The simple algorithm partitions elements into m roughly equal sets, while the complex algorithm improves the approximation ratio.
- Algorithms: Algorithm 5 outputs a solution of value at most 4p ln n · B with probability at least p.It assumes a feasible instance and uses random sampling to find disjoint sets with low function-value-to-size ratio.
6 Approximating submodular functions everywhere
The paper proves a stronger lower bound for everywhere-approximating monotone submodular functions and gives a near-matching algorithm for monotone two-partition functions.
- Lower bound: Polynomially many oracle queries cannot approximate monotone submodular functions to a factor o(√).The lower bound reuses the hard functions from the submodular minimization lower bound.
- Lower bound: The lower bound follows because one output must simultaneously approximate two indistinguishable functions whose values on R differ by α/β = √.The indistinguishability holds with high probability for polynomial-query algorithms.
- Monotone two-partition functions: Algorithm 6 either reconstructs a two-partition function exactly or outputs a uniform approximation based on sampled function values.Different values on equal-sized sampled sets trigger exact recovery; otherwise the algorithm constructs ˆf from queried values.
- Monotone two-partition functions: With probability at least p, Algorithm 6 guarantees ˆf(S) ≤ f(S) ≤ 2√ n · ˆf(S) for every set S.The proof uses monotonicity, submodularity, and a structural lemma for balanced pairs.
- Monotone two-partition functions: A two-partition function depends only on |S ∩ R| and |S ∩ ¯R|.The algorithm exploits this restricted structure to reason about pairs (k, l) representing these two intersection sizes.
- Monotone two-partition functions: Balanced pairs are sampled so that their function values depend only on total set size when Algorithm 6 reaches its final step.The proof uses concavity along balanced pairs and compares increments on balanced and one-sided pairs.