Color constrained combinatorial optimization problems (Q1178732): Difference between revisions

Let \(E\) be a finite set and let \(c: E\to Z_ +\) be a non-negative integer cost function. Given subsets \(E_ 1,\dots,E_ K\subseteq E\) (colors) and \(\ell_ 1,\dots,\ell_ K\in Z\), find \(\min\sum_{e\in S}c(e)\) satisfying \(S\in{\mathcal S}\), \(| S\cap E_ k|=\ell_ k\), \(| S\cap\overline{E}_ k|=R-\ell_ k\), \(k=1,\dots,K\), where \(S\subseteq E\), \(\mathcal S\) is the set of feasible solutions, \(\overline {E}_ k=E\backslash E_ k\) and \(R=\max\{| S|:\;S\subseteq E,\;S\in{\mathcal S}\}\). The authors show how to reduce this problem to a parametric problem with paiwise disjoint colors and derive as special cases polynomial algorithms for one instance of a 3-matroid intersection problem and colored bipartite matching problems.