  In computing, as in many aspects of life, changes incur cost. Many
optimization problems are formulated as a one-time instance starting from
scratch. However, a common case that arises is when we already have a set of
prior assignments, and must decide how to respond to a new set of constraints,
given that each change from the current assignment comes at a price. That is,
we would like to maximize the fitness or efficiency of our system, but we need
to balance it with the changeout cost from the previous state.
  We provide a precise formulation for this tradeoff and analyze the resulting
{\em stable extensions} of some fundamental problems in measurement and
analytics. Our main technical contribution is a stable extension of PPS
(probability proportional to size) weighted random sampling, with applications
to monitoring and anomaly detection problems. We also provide a general
framework that applies to top-$k$, minimum spanning tree, and assignment. In
both cases, we are able to provide exact solutions, and discuss efficient
incremental algorithms that can find new solutions as the input changes.
