A multiply constrained matroid optimization problem (Q1825757): Difference between revisions

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.