@inproceedings{kesselheim2024supermodular,
author = {Kesselheim, Thomas and Molinaro, Marco and Singla, Sahil},
title = {Supermodular Approximation of Norms and Applications},
booktitle = {2024 Symposium on the Theory of Computing},
year = {2024},
month = {April},
abstract = {Many classical problems in theoretical computer science involve norm, even if implicitly; for
example, both XOS functions and downward-closed sets are equivalent to some norms. The last
decade has seen a lot of interest in designing algorithms beyond the standard ℓp norms.
Despite notable advancements, many existing methods remain tailored to specific problems,
leaving a broader applicability to general norms less understood. This paper investigates the
intrinsic properties of ℓp norms that facilitate their widespread use and seeks to abstract these
qualities to a more general setting.
We identify supermodularity—often reserved for combinatorial set functions and characterized by monotone gradients—as a defining feature beneficial for the ℓp norm. We introduce the notion
of p-supermodularity for norms, asserting that a norm is p-supermodular if its pth power function exhibits supermodularity. The association of supermodularity with norms offers a new lens
through which to view and construct algorithms.
Our work demonstrates that for a large class of problems p-supermodularity is a sufficient
criterion for developing good algorithms. This is either by reframing existing algorithms for
problems like Online Load-Balancing and Bandits with Knapsacks through a supermodular
lens, or by introducing novel analyses for problems such as Online Covering, Online Packing,
and Stochastic Probing. Moreover, we prove that every symmetric norm can be approximated by
a p-supermodular norm. Together, these recover and extend several results from the literature,
and support p-supermodularity as a unified theoretical framework for optimization challenges
centered around norm-related problems},
url = {http://approjects.co.za/?big=en-us/research/publication/supermodular-approximation-of-norms-and-applications/},
}