Algorithms for measuring perturbality in matroid optimization
A matroid \((E,\mathcal I)\) and two nonnegative functions \(w\) and \(c\) on \(E\) are given. \(w(e)\) is the weight of an element \(e\in E\) and \(c(e)\) measures the cost of increasing \(w(e)\) by one unit. \(F(b)\) is the maximum increase of the weight of a minimum weight base while the weights are increased by a total cost of at most \(b\). The authors present a polynomial algorithm for computing \(F(b)\).
scientific article; zbMATH DE number 1336283