Least and most colored bases (Q2381817)

From the authors' abstract: ``Consider a matroid \({\mathcal M} = (E,{\mathcal B})\), where \({\mathcal B}\) denotes the family of bases of \({\mathcal M}\), and assign a color \(c(e)\) to every element \(e \in E\) (the same color can go to more than one element). The palette of a subset \(F\) of \(E\), denoted by \(c(F)\), is the image of \(F\) under \(c\). Assume also that colors have prices (in the form of a function \(\pi(\ell)\), where \(\ell\) is the label of a color), and define the chromatic price as \(\pi(F) =\sum_{\ell\in c(F)}\pi(\ell)\). We consider the following problem: find a base \(B \in {\mathcal B}\) such that \(\pi(B)\) is minimum. We show that the greedy algorithm delivers an \(\ln r({\mathcal M})\)-approximation of the unknown optimal value, where \(r({\mathcal M})\) is the rank of the matroid \({\mathcal M}\). By means of a reduction from SETCOVER, we prove that the \(\ln r({\mathcal M})\) ratio cannot be further improved, even in the special case of partition matroids, unless \(\text{NP} \subseteq \text{DTIME}(n^{\log \log n})\). The results apply to the special case where \({\mathcal M}\) is a graphic matroid and where the prices \(\pi(\ell)\) are restricted to be all equal. This speial case was previously known as the minimum label spanning tree (MLST) problem. For the MLST, our results improve over the \(\ln(n-1)+1\) ratio achieved by \textit{Y. Wan, G. Chen} and \textit{Y. Xu} [Inf. Process. Lett. 84, No.~2, 99--101 (2002; Zbl 1042.68055)]. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function \(\pi(F)\), where \(F\) is a common independent set on matroids \({\mathcal M}_1,\dots, {\mathcal M}_k\) and, more generally, to independent systems characterized by the \(k\)-for-1 property.'' The authors conclude this paper by giving a few open problems.