A multiply constrained matroid optimization problem
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.
- Matroid optimization with generalized constraints
- Constrained matroidal bottleneck problems
- Convex Matroid Optimization
- Multi-constrained matroidal knapsack problems
- Decomposable multi-parameter matroid optimization problems.
- A parameterized view on matroid optimization problems
- A Parameterized View on Matroid Optimization Problems
- Computation in multicriteria matroid optimization
- scientific article; zbMATH DE number 4027489
- Matroid optimization problems with monotone monomials in the objective
- A weighted matroid intersection algorithm
- Efficient algorithms for a family of matroid intersection problems
- scientific article; zbMATH DE number 4049649 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- Matroid optimization with the interleaving of two ordered sets
- Setup optimization problems with matroid structure
- A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
- The optimal base of a matroid with three-type constraints
- Color constrained combinatorial optimization problems
- A constrained independent set problem for matroids
- Optimization problems with color-induced budget constraints
- Constrained spanning trees and the traveling salesman problem
- Multi-constrained matroidal knapsack problems
- Matroid optimization with generalized constraints
- Matroid optimization problems with monotone monomials in the objective
- Least and most colored bases
- Objective functions with redundant domains
- Optimization problems with color-induced budget constraints
- k-Best constrained bases of a matroid
- A Parameterized View on Matroid Optimization Problems
- Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
- scientific article; zbMATH DE number 140090 (Why is no real title available?)
- Biobjective optimization problems on matroids with binary costs
- Color-constrained arborescences in edge-colored digraphs
- Arborescences and shortest path trees when colors matter
This page was built for publication: A multiply constrained matroid optimization problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825757)
