Universal set families for maximization of nonnegative submodular and XOS functions

Chandra Chekuri, Richard Ueltzen, Jan Vondrak

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_{\ge 0}$ in a certain class, we have $$\max_{S \in…