Changing Bases: Multistage Optimization for Matroids and Matchings

  • Anupam Gupta
  • Kunal Talwar
  • Udi Wieder


Published by Springer Verlag

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 Tt at each step: we pay ct(Tt) for the cost of the tree at time t, and also | Tt setminus Tt-1 | for the number of edges changed at this step. Our main result is a polynomial time O(log m log r)-approximation to the online multistage matroid maintenance problem, where m is the number of elements/edges and r is the rank of the matroid. This improves on results of Buchbinder et al. who addressed the fractional version of this problem under uniform acquisition costs, and Buchbinder, Chen and Naor who studied the fractional version of a more general problem. We also give an O(log m) 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.

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(n1-ε)-approximation to the multistage matching maintenance problem, even in the offline case.