hide
Free keywords:
-
Abstract:
The robustness function of an optimization problem measures the maximum
change in the value of its optimal solution that can be produced by changes of
a given total magnitude on the values of the elements in its input. The
problem of computing the robustness function of matroid optimization problems is
studied under two cost models: the discrete model, which allows the
removal of elements from the input, and the continuous model, which
permits finite changes on the values of the elements in the input.
For the discrete model, an $O(\log k)$-approximation algorithm is presented
for computing the robustness function of minimum spanning trees, where $k$ is
the number of edges to be removed. The algorithm uses as key subroutine a
2-approximation algorithm for the problem of dividing a graph into the maximum
number of components by removing $k$ edges from it.
For the continuous model, a number of results are presented. First, a general
algorithm is given for computing the robustness function of any matroid. The
algorithm runs in strongly polynomial time on matroids with a strongly
polynomial time independence test. Faster algorithms are also presented for
some particular classes of matroids: (1) an $O(n^3m^2 \log (n^2/m))$-time
algorithm for graphic matroids, where $m$ is the number of elements in the
matroid and $n$ is its rank, (2) an $O(mn(m+n^2)|E|\log(m^2/|E|+2))$-time
algorithm for transversal matroids, where $|E|$ is a parameter of the matroid,
(3) an $O(m^2n^2)$-time algorithm for scheduling matroids, and (4) an
$O(m \log m)$-time algorithm for partition matroids. For this last class of
matroids an optimal algorithm is also presented for evaluating the robustness
function at a single point.
