A multiply constrained matroid optimization problem
type: Item
instance of: scholarly article
title: A multiply constrained matroid optimization problem
zbMATH Open document ID: 0684.90072
DOI: 10.1016/0012-365X(88)90149-5
author: Yanyan Li
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: Let \(M=(E,J)\) be a matroid, let E be partitioned sets \(R_ i\), \(i=1,...,r\), \(E=R_ 1\cup...\cup R_ r\), and \(\ell =(\ell_ 1,...,\ell_ r)\in Z^ r_+\). For a basis B the following side constraints are considered: \[ (1)\quad | B\cap R_ i| \leq \ell_ i,\quad i=1,...r. \] For a given cost function C: \(E\to Z\) the multi-color matroid optimization problem is defined as the problem of finding a minimum cost basis satisfying the conditions (1). Applications of this problem are: (1) Finding a minimum spanning tree in the network; (2) Finding a minimum cost schedule, containing at most \(\ell_ i\) jobs of job class \(R_ i.\) A direct algorithm for the multi-colour matroid optimization problem is proposed. This algorithm proceeds in two stages: in a preprocessing phase a minimum cost basis B of the matroid M is found (without constraints (1)); then, in the second (and main) stage a sequence of bases is generated, starting with B such the number of elements violating (1) strictly decreases. In this stage an optimal solution is found.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 4121763
zbMATH Keywords: matroid
zbMATH Keywords: multi-color matroid optimization problem
zbMATH Keywords: minimum cost basis
zbMATH Keywords: minimum spanning tree
zbMATH Keywords: minimum cost schedule
zbMATH Keywords: preprocessing phase
reviewed by: Oleg A. Shcherbina
MaRDI profile type: Publication
cites work: A weighted matroid intersection algorithm
cites work: Efficient algorithms for a family of matroid intersection problems
cites work: Matroid optimization with the interleaving of two ordered sets
cites work: Q3786484
cites work: Q4130999
cites work: Q4111952
Recommended article: Matroid optimization with generalized constraints
Recommended article: Constrained matroidal bottleneck problems
Recommended article: Convex Matroid Optimization
Recommended article: Multi-constrained matroidal knapsack problems
Recommended article: Decomposable multi-parameter matroid optimization problems.
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: Q3768918
Recommended article: Matroid optimization problems with monotone monomials in the objective
description: scientific article; zbMATH DE number 4121763