Algorithms for measuring perturbability in matroid optimization

The perturbability function of a matroid measures the maximum increase in t he weight of its minimum weight bases that can be produced by increases of a given total cost on the weights of its elements. We present an algorithm for computing this function that runs in strongly polynomial time for matro ids in which independence can be tested in strongly polynomial time. Furthe rmore, for the case of transversal matroids we are able to take advantage o f their special structure to design a faster algorithm for computing the pe rturbability function.