  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 $\ell_p$ norms $\|\cdot \|_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 $\ell_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
$ \|\cdot\|_p^p$. We introduce the notion of $p$-supermodularity for norms,
asserting that a norm is $p$-supermodular if its $p^{th}$ 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.
