Algorithms for Measuring Perturbability in Matroid Optimization |
| |
Authors: | Greg N. Frederickson Roberto Solis-Oba |
| |
Affiliation: | (1) Department of Computer Science, Purdue University; West Lafayette IN 47907, USA; E-mail: gnf@cs.purdue.edu, US;(2) Max Planck Institut für Informatik; 66123 Saarbrücken, Germany; E-mail: solis@mpi-sb.mpg.de, DE |
| |
Abstract: | perturbability function of a matroid measures the maximum increase in the weight of its minimum weight bases that can be produced by increases of a given total cost on the weights of its elements. We present an algorithm for computing this function that runs in strongly polynomial time for matroids in which independence can be tested in strongly polynomial time. Furthermore, for the case of transversal matroids we are able to take advantage of their special structure to design a faster algorithm for computing the perturbability function. Received: June 13, 1997 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 05B35, 0504, 68R05 |
本文献已被 SpringerLink 等数据库收录! |