(/forwarded by Stan Sclove, Secretary, Classification Society/ )
*********************************************************************
(/Apologies for cross-posting/ )
The Tenth DIMACS Implementation Challenge:
Graph Partitioning and Graph Clustering
http://www.cc.gatech.edu/dimacs10/
=== 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.
Motivation:
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?
Goals:
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.
Testbed:
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
above.
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.
Committees:
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