Organizing Committee
- David Johnson
Columbia University - Thorsten Koch
Konrad-Zuse-Zentrum für Informationstechnik (ZIB) - Renato Werneck
Princeton University - Martin Zachariasen
University of Copenhagen
Abstract
The DIMACS Implementation Challenges address questions of determining realistic algorithm performance where worst case analysis is overly pessimistic and probabilistic models are too unrealistic: experimentation can provide guides to realistic algorithm performance where analysis fails.
The 11th Implementation Challenge is dedicated to the study of Steiner Tree problems (broadly defined), bringing together research in both theory and practice. Broadly speaking, the goal of a Steiner Tree problem is to find the cheapest way of connecting a set of objects. In most common variants, these objects are either points in a metric space or a subset of the vertices of a network, and the goal is to find a tree that connects all of them.
The main aim of the challenge is to create a reproducible picture of the state-of-the-art in Steiner Tree problems. Phases 1 and 2 of this challenge - the collection and improvement of testbeds and algorithm development and evaluation - began in June 2013. During this workshop, participants will present pre-submitted and vetted papers devoted to Steiner Tree problems. By the end of the workshop, competition results will be announced in anticipation of Phase 3, which will include the final revision of papers for challenge proceedings.
Find more details about DIMACS, and this particular Challenge.
Co-sponsors
- Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
- The DIMACS Special Focus on Information Sharing and Dynamic Data Analysis
- The Institute for Computational and Experimental Research in Mathematics (ICERM)
Confirmed Speakers & Participants
Talks will be presented virtually or in-person as indicated in the schedule below.
- Speaker
- Poster Presenter
- Attendee
- Virtual Attendee
-
Markus Blumenstock
Johannes Gutenberg-Universität Mainz
-
Alfredo Braunstein
Politecnico di Torino
-
Oleg Burdakov
Linköping University
-
Krzysztof Ciebiera
University of Warsaw
-
Mohammed El-Kebir
Brown University
-
Rasmus Fonseca
University of Copenhagen
-
Zhanghua Fu
Universite d'Angers
-
Gerald Gaurath
NONE
-
Alessandro Hill
Universiteit Antwerp
-
Pedro Hokama
State University of Campinas (UNICAMP)
-
David Johnson
Columbia University
-
Gunnar Klau
Center for Mathematics and Computer Science (CWI)
-
Thorsten Koch
Konrad-Zuse-Zentrum für Informationstechnik (ZIB)
-
Jakob Lemvig
Technical University of Denmark
-
Martin Luipersbeck
Universität Wien
-
Stephen Maher
Zuse Institute Berlin (ZIB)
-
Anna Paola Muntoni
Politecnico di Torino
-
Daniel Rehfeldt
Zuse Institute Berlin (ZIB)
-
Ludwig Schmidt
Massachusetts Institute of Technology
-
Yuji Shinano
Zuse Institute Berlin (ZIB)
-
Jannik Silvanus
Rheinische Friedrich-Wilhelms-Universität Bonn
-
Markus Sinnl
University of Vienna
-
Sophie Spirkl
Princeton University
-
David Warme
Group W., Inc.
-
Renato Werneck
Princeton University
-
Rupei Xu
University of Texas at Dallas
-
Martin Zachariasen
University of Copenhagen
Workshop Schedule
Thursday, December 4, 2014
Time | Event | Location | Materials |
---|---|---|---|
8:15 - 8:40am EST | Registration and Breakfast | 11th Floor Collaborative Space | |
8:40 - 9:00am EST | DIMACS Implementation Challenges: Past, Present, and Future | 11th Floor Lecture Hall | |
9:00 - 10:30am EST | Classical Steiner Problem in Graphs | 11th Floor Lecture Hall | |
10:30 - 10:50am EST | Coffee Break | 11th Floor Lecture Hall | |
10:50 - 12:20pm EST | Flexible Techniques | 11th Floor Lecture Hall | |
12:20 - 2:00pm EST | Lunch Break | 11th Floor Collaborative Space | |
2:00 - 3:30pm EST | Euclidean and Rectilinear Variants | 11th Floor Lecture Hall | |
3:30 - 4:00pm EST | Coffee Break | 11th Floor Collaborative Space | |
4:00 - 5:30pm EST | Constrained Variants | 11th Floor Lecture Hall | |
6:00 - 7:00pm EST | Reception | 11th Floor Collaborative Space |
Friday, December 5, 2014
Time | Event | Location | Materials |
---|---|---|---|
8:30 - 9:00am EST | Breakfast | 11th Floor Collaborative Space | |
9:00 - 10:30am EST | Prize-Collecting Variants | 11th Floor Lecture Hall | |
10:30 - 11:00am EST | Coffee Break | 11th Floor Collaborative Space | |
10:50 - 12:20pm EST | Extended Graph Problems | 11th Floor Lecture Hall | |
12:20 - 12:25pm EST | Group Photo | 11th Floor Lecture Hall | |
12:25 - 1:25pm EST | Lunch | 11th Floor Collaborative Space | |
1:30 - 3:00pm EST | Contest Results and Discussion | 11th Floor Lecture Hall |