(/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