Algorithms for measuring perturbality in matroid optimization
type: Item
instance of: scholarly article
title: Algorithms for measuring perturbality in matroid optimization
zbMATH Open document ID: 0921.05020
author: Greg N. Frederickson
author: Roberto Solis-Oba
published in: Combinatorica
publication date: 1999-09-14T00:00:00Z
review text: A matroid \((E,\mathcal I)\) and two nonnegative functions \(w\) and \(c\) on \(E\) are given. \(w(e)\) is the weight of an element \(e\in E\) and \(c(e)\) measures the cost of increasing \(w(e)\) by one unit. \(F(b)\) is the maximum increase of the weight of a minimum weight base while the weights are increased by a total cost of at most \(b\). The authors present a polynomial algorithm for computing \(F(b)\).
reviewed by: András Recski
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 1336283
zbMATH Keywords: matroid optimization
MaRDI profile type: Publication
full work available at URL: s004930050036
OpenAlex ID: W1966974494
DOI: 10.1007/S004930050036
Recommended article: Q4871759
Recommended article: A parameterized view on matroid optimization problems
Recommended article: A Parameterized View on Matroid Optimization Problems
Recommended article: Computation in multicriteria matroid optimization
Recommended article: Q3717069
Recommended article: Computing girth and cogirth in perturbed graphic matroids
Recommended article: Q5752583
Recommended article: Random pseudo-polynomial algorithms for exact matroid problems
Recommended article: Convex Matroid Optimization
Recommended article: Q4789255
description: scientific article; zbMATH DE number 1336283