Consider a matroid M=(E,B) , where B denotes the family of bases of 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(l), where l is the label of a color), and define the chromatic price as : pi(F)=sum pi(l). We consider the following problem: find a base B in B such that pi(B) is minimum. We show that the greedy algorithm delivers a ln r(M)-approximation of the unknown optimal value, where r(M) is the rank of matroid M. By means of a reduction from SetCover, we prove that the ln r(M) ratio can not be further improved, even in the special case of partition matroids, unless NP is a contained in the complexity class DTIME. The results apply to the special case where M is a graphic matroid and where the prices pi(l) 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 pi(F), where F is a common independent set on matroids M(1),...,M(k) and, more generally, to independent systems characterized by the k-for-1 property.

### Least and most colorable bases

#### Abstract

Consider a matroid M=(E,B) , where B denotes the family of bases of 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(l), where l is the label of a color), and define the chromatic price as : pi(F)=sum pi(l). We consider the following problem: find a base B in B such that pi(B) is minimum. We show that the greedy algorithm delivers a ln r(M)-approximation of the unknown optimal value, where r(M) is the rank of matroid M. By means of a reduction from SetCover, we prove that the ln r(M) ratio can not be further improved, even in the special case of partition matroids, unless NP is a contained in the complexity class DTIME. The results apply to the special case where M is a graphic matroid and where the prices pi(l) 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 pi(F), where F is a common independent set on matroids M(1),...,M(k) and, more generally, to independent systems characterized by the k-for-1 property.
##### Scheda breve Scheda completa Scheda completa (DC)
2007
Benati, Stefano; Rizzi, Romeo; F., Maffioli
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11572/28346`
• ND
• 6
• ND