Consider a matroid
, where
denotes the family of bases of
, and assign a color
c(e) to every
element eE (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
π(ℓ), where
ℓ is the label of a color), and define the chromatic price as:
π(F)=∑ℓc(F)π(ℓ). We consider the following problem: find a base
such that
π(B) is minimum. We show that the greedy algorithm delivers a
-approximation of the unknown optimal value, where
is the rank of matroid
. By means of a reduction from S
ETC
OVER, we prove that the
ratio cannot be further improved, even in the special case of
partition matroids, unless
. The results apply to the special case where
is a graphic matroid and where the prices
π(ℓ) are restricted to be all equal. This special 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 Wan, Chen and Xu in 2002. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function
π(F), where
F is a common independent set on matroids
and, more generally, to independent systems characterized by the
k-for-1 property.