English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Robustness analysis in combinatorial optimization

Frederickson, G. N., & Solis-Oba, R.(1998). Robustness analysis in combinatorial optimization (MPI-I-1998-1-011). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0014-7BD3-5 Version Permalink: http://hdl.handle.net/21.11116/0000-0001-7524-3
Genre: Report

Files

show Files
hide Files
:
MPI-I-98-1-011.pdf (Any fulltext), 504KB
Name:
MPI-I-98-1-011.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Frederickson, Greg N.1, Author
Solis-Oba, Roberto2, Author              
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
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.

Details

show
hide
Language(s): eng - English
 Dates: 1998
 Publication Status: Published in print
 Pages: 66 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-1998-1-011
BibTex Citekey: FredericksonSolis-Oba98
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -