( forwarded by Stan Sclove, Secretary, Classification Society )

      ( Apologies for cross-posting )

      The Tenth DIMACS Implementation Challenge: 
      Graph Partitioning and Graph Clustering 

      === Call for Participation  ===


On behalf of the Center for Discrete Mathematics and Theoretical 
Computer Science DIMACS, the organizing committee invites 
participation in an Implementation Challenge focusing on Graph 
Partitioning and Graph Clustering. The Implementation Challenge 
starts in February 2011 with the collection of testbeds. 
Participants are invited to carry out research projects related 
to the problem area and to present research papers at the 
Challenge's workshop to be held in Atlanta (Georgia, USA)
on February 13/14, 2012. Refereed workshop proceedings will
be published in the AMS-DIMACS book series.


Graph partitioning and graph clustering are ubiquitous subtasks 
in many application areas. Generally speaking, both techniques 
aim at the identification of vertex subsets with many internal 
and few external edges. To name only a few, problems addressed by 
graph partitioning and graph clustering algorithms are: What are 
the communities within an (online) social network? How do I speed 
up a numerical simulation by mapping it efficiently onto a 
parallel computer? How must components be organized on a computer 
chip such that they can communicate efficiently with each other? 
What are the segments of a digital image? Which functions are 
certain genes (most likely) responsible for?


The goals of the Implementation Challenge are (i) to determine 
how algorithms depend on the structure of the underlying data 
sets, (ii) to determine realistic algorithm performance, and 
(iii) to obtain a reproducible picture of the state-of-the-art in 
the area of graph partitioning and graph clustering algorithms. 
To this end we are identifying a standard set of benchmark 
instances and generators. Based on our initial proposals and 
after a discussion with the community, we would like to establish 
the most appropriate problem formulations and objective functions 
for different applications.


We invite researchers from various application areas to provide 
interesting data sets for graph partitioning and graph clustering 
problems. Contributions could consist either of sample data sets 
from a true application or of realistic instance generators 
resembling practical data sets. Also, we invite the specification 
of interesting objective functions based on real-world 
applications. Our goal is to construct a modern library of test 
problems reflecting current input sizes. The library will be 
available for study both during and after the Challenge.

  Developing Graph Partitioning and Graph Clustering Algorithms:

Algorithms may be developed for one or more categories (graph 
partitioning / graph clustering, each with different objectives) 
of the Challenge. Projects may involve either public domain or 
proprietary codes. More details on the structure of the Challenge 
will be announced later, please refer to the Challenge website 

  How to Participate:

All information on the Challenge is available on the Challenge website
above. In particular, to register for the Challenge, please visit
http://www.cc.gatech.edu/dimacs10/mailing.shtml for information
on how to subscribe to the mailing list.
Note that neither DIMACS nor the committee members can provide financial
support for research projects or machine cycles for the experiments.


The organizing committee consists of the coordinators 
David A. Bader (Georgia Institute of Technology), 
Peter Sanders (Karlsruhe Institute of Technology) and 
Dorothea Wagner (Karlsruhe Institute of Technology), 
assisted by 
Henning Meyerhenke (Georgia Institute of Technology). 

The advisory board members are Bruce Hendrickson 
(Sandia National Laboratories), David S. Johnson (AT&T Labs - 
Research), and Chris Walshaw (University of Greenwich). 



                       Stanley L. Sclove,  Ph.D.       
                             S t a t i s t i c i a n 
           Professor, University of Illinois at Chicago

Information & Decision Sciences Dept (MC 294) . . ofc (312) 996-2681
College of Business Administration        .  .  .  .   dept (312) 996-2676
University of Illinois at Chicago            .  .  .  .  .    fax (312) 413-0385
601 S. Morgan Street               .  .  .  .  .  .  .  .  .     [log in to unmask]
Chicago, IL 60607-7124, U.S.A        .  .  .  .  .  www.uic.edu/~slsclove

---------------------------------------------- CLASS-L list. Instructions: http://www.classification-society.org/csna/lists.html#class-l