Changing bases: Multistage optimization for matroids and matchings

Anupam Gupta, Kunal Talwar, Udi Wieder

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. 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 Tt at each step: we pay ct (Tt) for the cost of the tree at time t, and also |Tt \Tt-1| for the number of edges changed at this step. Our main result is a polynomial time O(logm logr)-approximation to the online 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. [7] who addressed the fractional 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 O(logm) 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 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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PublisherSpringer Verlag
Number of pages13
EditionPART 1
ISBN (Print)9783662439470
StatePublished - 2014
Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
Duration: Jul 8 2014Jul 11 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8572 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Changing bases: Multistage optimization for matroids and matchings'. Together they form a unique fingerprint.

Cite this