This paper is motivated by the fact that many systems need to be maintained continually while the underlying costs change over time. The challenge then is to continually maintain near-optimal solutions to the underlying optimization problems, without creating too much churn in the solution itself. We model this as a multistage combinatorial optimization problem where the input is a sequence of cost functions (one for each time step); while we can change the solution from step to step, we incur an additional cost for every such change.

We first study the multistage matroid maintenance problem, where we need to
maintain a base of a matroid in each time step under the changing cost functions
and acquisition costs for adding new elements. The online version of this problem
generalizes onine paging, and is a well-structured case of the metrical task
systems. E.g., given a graph, we need to maintain a spanning tree
*T _{t}* at each step: we pay

We also study the perfect matching version of the problem, where we must
maintain a perfect matching at each step under changing cost functions and costs
for adding new elements. Surprisingly, the hardness drastically increases: for
any constant *ε>0*, there is no
*O(n ^{1-ε})*-approximation to the multistage matching
maintenance problem, even in the offline case.