Minimum multiplicity edge coloring via orientation

We study an edge coloring problem in multigraphs, in which each node incurs a cost equal to the number of appearances of the most frequent color among those received by its incident edges. We seek an edge coloring with a given number w of colors, that minimizes the total cost incurred by the nodes of the multigraph. We consider a class of approximation algorithms for this problem, which are based on orienting the edges of the multigraph, then grouping appropriately the incoming and outgoing edges at each node so as to construct a bipartite multigraph of maximum degree  w, and finally obtaining a proper edge coloring of this bipartite multigraph. As shown by Nomikos et al. (2001), simply choosing an arbitrary edge orientation in the first step yields a 2-approximation algorithm. We investigate whether this approximation ratio can be improved by a more careful choice of the edge orientation in the first step. We prove that, assuming a worst-case bipartite edge coloring, this is not possible in the asymptotic sense, as there exists a family of instances in which any orientation gives a solution with cost at least 2−Θ(1w) times the optimal. On the positive side, we show how to produce an orientation which results in a solution with cost within a factor of 2−12w of the optimal, thus yielding an approximation ratio strictly better than 2. This improvement is important in view of the fact that this graph-theoretic problem models, among others, wavelength assignment to communication requests in multifiber optical star networks. In this context, the parameter w corresponds to the number of available wavelengths per fiber, which is limited in practice due to technological constraints.