# Supermodular Approximation of Norms and Applications

arXiv: https://arxiv.org/abs/2406.15180 · HTML: https://mlsanity.com/paper/2406.15180/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2024.

## Built on by (most cited first, 1 of 1)

- [Online Algorithms via Minimax and Posterior Matching](https://mlsanity.com/paper/2608.01616/) (2026)

## Abstract (arXiv)

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 |· |p. 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  |·|pp. 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.