Changing Bases: Multistage Optimization for Matroids and Matchings

<p>This paper is motivated by the fact that many systems need to be maintained continually while the underlying costs change over time. The challenge is to continually maintain near-optimal solutions to an underlying optimization problem, 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.</p> <p>We first study the multistage matroid maintenance problem, where we need to maintain a base of a matroid in each time step under changing cost functions and acquisition costs for adding new elements. The online version generalizes online paging. E.g., given a graph, we need to maintain a spanning tree <em>T</em> <em>t</em> at each step: we pay <em>c</em> <em>t</em> (<em>T</em> <em>t</em> ) for the cost of the tree at time <em>t</em>, and also | <em>T</em> <em>t</em>  ∖ <em>T</em> <em>t</em> − 1 | for the number of edges changed at this step. Our main result is a polynomial time <em>O</em>(log<em>m</em> log<em>r</em>)-approximation to the online problem, where <em>m</em> is the number of elements/edges and <em>r</em> is the rank of the matroid. This improves on results of Buchbinder et al. [7] who addressed the <em>fractional</em> version of this problem under uniform acquisition costs, and Buchbinder, Chen and Naor [8] who studied the fractional version of a more general problem. We also give an <em>O</em>(log<em>m</em>) approximation for the offline version of the problem. These bounds hold when the acquisition costs are non-uniform, in which case both these results are the best possible unless P=NP.</p> <p>We also study the perfect matching version of the problem, where we 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 <em>ε</em> > 0, there is no <em>O</em>(<em>n</em> 1 − <em>ε</em> )-approximation to the multistage matching maintenance problem, even in the offline case.</p>