Efficient algorithms for robustness in resource allocation and scheduling problems

摘要

The robustness function of an optimization (minimization) problem measures the maximum increase in the value of its optimal solution that can be produced by spending a given amount of resources increasing the values of the elements in its input. We present efficient algorithms for computing the robustness function of resource allocation and scheduling problems that can be modeled with partition and scheduling matroids. For the case of scheduling matroids, we give an O(m{sup}2n{sup}2) time algorithm for computing a complete description of the robustness function, where m is the number of elements in the matroid and n is its rank. For partition matroids, we give two algorithms: one that computes the complete robustness function in O(m log m) time, and other that optimally evaluates the robustness function at only a specified point.