Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00172
Fast edge colorings with fixed number of colors to minimize imbalance
Vol. 12, no. 4, pp. 401417, 2008. Regular paper.
Abstract We study the following optimization problem:
the input is a multigraph G=(V,E) and
an integer parameter g. A feasible solution consists of a
(not necessarily proper) coloring of E with colors 1, 2, …, g.
Denote by d(v,i) the number of edges colored i incident to v.
The objective is to minimize ∑_{ v ∈ V} max_{i} d(v,i),
which roughly corresponds to the "imbalance" of the edge coloring.
This problem was proposed by Berry and Modiano (INFOCOM 2004),
with the goal of optimizing the deployment of tunable ports in optical networks.
Following them we call the optimization problem MTPS 
Minimum Tunable Port with Symmetric Assignments.
Among other results, they give a reduction from Edge Coloring showing that MTPS
is NPHard and then implicitly give a 2approximation algorithm.
We give a (3/2)approximation algorithm. Key to this problem
is the following question: given a multigraph G=(V,E) of maximum degree g,
what fraction of the vertices can be properly edgecolored in a coloring
with g colors, where a vertex is properly edgecolored if
the edges incident to it have different colors?
Our main lemma states that there is such a coloring with half of the vertices
properly edgecolored. For g ≤ 4, two thirds of vertices can
be made properly edgecolored.
Our algorithm is based on g Maximum Matching computations
(total running time O(g m √{n + m/g}), where n=V and m=E) and
a local optimization procedure, which by itself gives a 2approximation.
An interesting analysis gives an expected O( (g n + m) log(gn +m) )
running time for the local optimization procedure.

Submitted: June 2007.
Reviewed: July 2008.
Revised: September 2008.
Accepted: September 2008.
Final: November 2008.
Published: December 2008.
Communicated by
Susanne Albers

Journal Supporters
