Computational Symposium Announcement
Graph Coloring and Generalizations

A Computational Symposium will be held in conjunction with Constraint
Programming 2002 at Cornell University, Ithaca, NY USA September 7-8,
2002.  The purpose of this Symposium is to encourage research on
computational methods for combinatorial optimization problems, to
evaluate alternative approaches using a common testbed, and to
stimulate discussion on present and future directions in computational
combinatorial optimization.  

The Symposium will be on the topic "Graph Coloring and
Generalizations".  This topic was chosen due to the wide applicability
of graph coloring and the variety of solution approaches that have
been proposed.  This symposium builds off of a DIMACS Computational
Challenge from the fall of 1993, where graph coloring was one of the
problems addressed.  In addition to the basic graph coloring problem,
results are also solicited for the related problems of
"multi-coloring" (assigning multiple colors to each node) and
bandwidth allocation models (those with minimum difference
requirements on the colors on adjacent nodes).

Possible topics suitable for the Symposium include:

-- Exact algorithms for graph coloring
   -- Constraint programming
   -- Integer programming
   -- Semidefinite programming
   -- Nonlinear approaches

-- Heuristic approaches
   -- Metaheuristics
   -- Incomplete methods

-- Applications and Instances
   -- Instance generators
   -- Applications and specially structured instances

-- Evaluation of Methods
   -- Methods for algorithm comparison
   -- Tools for experimental algorithmics

All papers should have some computational aspect.

In addition to the Symposium, there will be a refereed volume of a
selection of papers presented.

The organizers of this conference are

   David Johnson, AT&T Labs
   Anuj Mehrotra, University of Miami
   Michael Trick, Carnegie Mellon

An additional Program Committee will be appointed.

An important part of this symposium is a standard set of test
instances to allow comparisons between papers. We are soliciting
instances for the various problems under consideration. If you have
instances or generators that you think would be of interest, please
drop trick@cmu.edu a note. We would like to set the instance set by
May 1.

Schedule Outline

   Feb 15: Formal Announcement of Symposium
            -- Solicitation of "Test Instances" (due May 1)

   May 15:  Final specification of problems and Instances

   July 1:  Extended abstracts due (5-8 page descriptions of methods
            and computational results on test instances)

   July 15: Papers selected for presentation at Symposium

   September 7-8.  Symposium at Constraint Programming 2002, Cornell
            University, Ithaca, NY (while participants are encouraged
            to also attend CP 2002, attending only the Symposium is
            permitted).

   October 15.  Final version of paper submitted for refereeing

   Spring 2003.  Publication of special volume

This is a preliminary announcement:  more details will be forthcoming
on the web page for the Symposium:

http://mat.gsia.cmu.edu/COLORING02

If you are interested in this Symposium, please subscribe to the
mailing list given on that page.