# MPI-I-98-1-011

## Robustness analysis in combinatorial optimization

### Frederickson, Greg N. and Solis-Oba, Roberto

**MPI-I-98-1-011**. April** **1998, 66 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 1196 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-011

**BibTeX**
`@TECHREPORT{``FredericksonSolis-Oba98``,`

` AUTHOR = {Frederickson, Greg N. and Solis-Oba, Roberto},`

` TITLE = {Robustness analysis in combinatorial optimization},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-98-1-011},`

` MONTH = {April},`

` YEAR = {1998},`

` ISSN = {0946-011X},`

`}`