  Budgeted uncertainty sets have been established as a major influence on
uncertainty modeling for robust optimization problems. A drawback of such sets
is that the budget constraint only restricts the global amount of cost increase
that can be distributed by an adversary. Local restrictions, while being
important for many applications, cannot be modeled this way.
  We introduce new variant of budgeted uncertainty sets, called locally
budgeted uncertainty. In this setting, the uncertain parameters become
partitioned, such that a classic budgeted uncertainty set applies to each
partition, called region.
  In a theoretical analysis, we show that the robust counterpart of such
problems for a constant number of regions remains solvable in polynomial time,
if the underlying nominal problem can be solved in polynomial time as well. If
the number of regions is unbounded, we show that the robust selection problem
remains solvable in polynomial time, while also providing hardness results for
other combinatorial problems.
  In computational experiments using both random and real-world data, we show
that using locally budgeted uncertainty sets can have considerable advantages
over classic budgeted uncertainty sets.
