# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### An Asymptotic Approximation Scheme for Multigraph Edge Coloring

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Sanders, P., & Steurer, D. (2005). An Asymptotic Approximation Scheme for Multigraph
Edge Coloring. In *Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)*
(pp. 897-906). Philadelphia, USA: SIAM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-259E-2

##### Abstract

The edge coloring problem asks for assigning colors from a minimum number of
colors to edges of a graph such that no two edges with the same
color are incident to the same node. We give polynomial time algorithms
for approximate edge coloring of multigraphs, i.e., parallel
edges are allowed. The best previous algorithms achieve a
fixed constant approximation factor plus a small additive offset.
Our algorithms achieve arbitrarily good approximation factors
at the cost of slightly larger additive term.
In particular, for any $\epsilon>0$ we achieve
a solution quality of $(1+\epsilon)\opt+\Oh{1/\epsilon}$.
The execution times of one algorithm are independent of $\epsilon$ and
polynomial in the number of nodes and
the \emph{logarithm} of the maximum edge multiplicity.