Universal sets approximate best solutions for submodular and XOS functions
Universal set families for maximization of nonnegative submodular and XOS functions
Data Structures and Algorithms
Summary
Finding the best subset that maximizes certain functions can be very challenging. The authors study how to create a small collection of universal sets that work well for a wide range of functions, guaranteeing a fraction of the best possible value. They show this collection can be very small for specific function types and prove limits on how good these universal families can get. Their work also introduces a new type of function and finds matching upper and lower bounds for approximations by polynomial-sized families.
What this means in practice
- •For combinatorial optimization engineers: Select small subsets to efficiently approximate optimal solutions for complex optimization problems modeled by submodular functions.
- •For network reliability teams: Use polynomial-size universal set families to guarantee good approximations of network connectivity metrics described by matroid representable functions.
A theory result. No direct application yet.
Authors
Chandra Chekuri, Richard Ueltzen, Jan Vondrak
Abstract
We consider the question of designing a universal family of sets $F \subset 2^{[n]}$ such that for any function $f:2^{[n]} \to R_{\geq 0}$ in a certain class, we have $$\max_{S \in F} f(S) \geq c(n) \cdot \max_{S \subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n) = Ω(\frac{\log \log n}{\log n})$, and there is a family of logarithmic size such that $c(n) = Ω(\frac{1}{\log n})$. We also prove that pairwise independence (which achieves a constant factor for graph cut functions), or even $k$-wise independence, does not imply a bound better than $O(\frac{1}{\sqrt{\log n}})$ for submodular functions. On the other hand, we prove that for any polynomially representable subclass of nonnegative submodular functions (such as the matroid connectivity functions for matroid representable over $F_q$), a constant-factor universal family of polynomial size always exists. For absolute XOS functions (a class that we introduce, in the form $f(S) = \max_i |\sum_{j \in S} w_{ij} + c_i|$ where $w_{ij}, c_i \in R$), we design a family of polynomial size such that $c(n) \geq \sqrt{\frac{\log n}{n}}$, and prove that there is no polynomial-size family achieving a factor better than $O(\sqrt{\frac{\log n}{n}})$.