\documentstyle[11pt]{article}
\title{Research Proposal for the Second DIMACS Implementation Challenge:\\
       Approximate Colorings of Geometric Graphs}
\author{Albert Gr\"af%
\thanks{Johannes Gutenberg-Universit\"at,
        Musikwissenschaftliches Institut,
        Bereich Musikinformatik,
        P.O.\ Box 3980, 6500 Mainz, Germany,
        \{ag,martin,wf\}@muwiinfa.geschichte.uni-mainz.de.
        Supported by the Department of Economics and Transportation
        of the Rhineland-Palatinate as part of the program of
        the association for research in media technology.}
\and Martin Stumpf\footnotemark[1] \and Gerhard Weissenfels\footnotemark[1]}
\date{December 3, 1992}
\setlength{\topmargin}{-.5in}
\addtolength{\textheight}{1.5in}
\addtolength{\textwidth}{\evensidemargin}
\addtolength{\textwidth}{\oddsidemargin}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\addtolength{\textwidth}{-1.0\oddsidemargin}
\addtolength{\textwidth}{-1.0\evensidemargin}
\setlength{\baselineskip}{20pt}
\begin{document}
%\bibliographystyle{alpha}
\maketitle
{\em Geometric graphs,\/} also known as {\em unit disk graphs,\/} are
intersection graphs of equal sized circles in the plane. Colorings of
geometric graphs arise in practical applications such as the frequency
assignment problem in broadcast networks \cite{Ha80,Ro91}. Since the
coloring problem remains NP-complete for this class of graphs \cite{CCJ90},
approximate solutions are of great interest.

In a recent experimental evaluation, different simulated annealing techniques
have been applied to graph coloring, with varying results \cite{JAMS91}. For
a class of randomly generated geometric graphs the annealing algorithms
were substantially outperformed by DSATUR, a successive augmentation
heuristic introduced by D.\ Br\'elaz \cite{Br79}.

It is easy to see that each ``greedy'' vertex-sequential heuristic like
DSATUR achieves a worst-case ratio of 6 between the number of colors it
uses and the actual chromatic number of a geometric graph.
(This comes from the fact that $\Delta(G)<6\omega(G)$ for each geometric
graph $G$, where $\Delta(G)$ and $\omega(G)$ denote the maximum vertex degree
and the maximum clique size of a graph $G$, respectively.) Improving on this,
we have developed two different approximation algorithms for coloring
geometric graphs. Our first algorithm achieves a performance ratio of 4
and is based on bipartite matching \cite{Gr92a}; the second one is a
3-approximation algorithm relying on network flow techniques as discussed
in \cite{Mo85}. More precisely, the algorithms are guaranteed to find,
respectively, $4\omega(G)$- and $3\omega(G)$-colorings of each geometric
graph $G$. Both algorithms require that the graph be given by its
model (i.e.\ a set of equal sized circles in the plane). Worst case analysis
indicates that there is a strong tradeoff between performance ratio
and running time in these algorithms. That is, our 3-approximation
algorithm achieves its better performance ratio compared to the
4-approximation algorithm only at the cost of a considerable increase
in asymptotic running time.

In the context of the challenge, we would like to investigate the
behavior of our algorithms in practice, how they can be further improved,
and how they compare to each other and to existing heuristics such as DSATUR
when applied to randomly generated instances of geometric graphs.
%\bibliography{dma}
\begin{thebibliography}{JAMS91}

\bibitem[Br{\'e}79]{Br79}
Daniel Br{\'e}laz.
\newblock New methods to color the vertices of a graph.
\newblock {\em Communications of the ACM}, 22(4):251--256, 1979.

\bibitem[CCJ90]{CCJ90}
Brent~N. Clark, Charles~J. Colbourn, and David~S. Johnson.
\newblock Unit disk graphs.
\newblock {\em Discrete Mathematics}, 86:165--177, 1990.

\bibitem[Gr{\"a}92]{Gr92a}
Albert Gr{\"a}f.
\newblock Permutative graph colorings.
\newblock Musikinformatik und Medientechnik 5/92, Johannes
  Gutenberg-Universit{\"a}t Mainz, Musikwissenschaftliches Institut, Bereich
  Musikinformatik, 1992.

\bibitem[Hal80]{Ha80}
W.K. Hale.
\newblock Frequency assignment: Theory and applications.
\newblock {\em Proc. IEEE}, 68:1497--1514, 1980.

\bibitem[JAMS91]{JAMS91}
D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C.~Schevon.
\newblock Optimization by simulated annealing: An experimental evaluation.
  {P}art {II}. {G}raph coloring and number partitioning.
\newblock {\em Operations Research}, 39:378--406, 1991.

\bibitem[M{\"o}h85]{Mo85}
Rolf~H. M{\"o}hring.
\newblock Algorithmic aspects of comparibility graphs and interval graphs.
\newblock In I.~Rival, editor, {\em Graphs and Orders}, pages 41--101. D.
  Reidel Publishing Company, 1985.

\bibitem[Rob91]{Ro91}
Fred~S. Roberts.
\newblock {$T$}-colorings of graphs: recent results and open problems.
\newblock {\em Discrete Mathematics}, 93:229--245, 1991.

\end{thebibliography}
\end{document}