Organizing Committee
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.

Image for "11th DIMACS Implementation Challenge in Collaboration with ICERM"

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

Workshop Schedule

Thursday, December 4, 2014
TimeEventLocationMaterials
8:15 - 8:40am ESTRegistration and Breakfast11th Floor Collaborative Space 
8:40 - 9:00am ESTDIMACS Implementation Challenges: Past, Present, and Future11th Floor Lecture Hall 
9:00 - 10:30am ESTClassical Steiner Problem in Graphs11th Floor Lecture Hall 
10:30 - 10:50am ESTCoffee Break11th Floor Lecture Hall 
10:50 - 12:20pm ESTFlexible Techniques11th Floor Lecture Hall 
12:20 - 2:00pm ESTLunch Break11th Floor Collaborative Space 
2:00 - 3:30pm ESTEuclidean and Rectilinear Variants11th Floor Lecture Hall 
3:30 - 4:00pm ESTCoffee Break11th Floor Collaborative Space 
4:00 - 5:30pm ESTConstrained Variants11th Floor Lecture Hall 
6:00 - 7:00pm ESTReception11th Floor Collaborative Space 
Friday, December 5, 2014
TimeEventLocationMaterials
8:30 - 9:00am ESTBreakfast11th Floor Collaborative Space 
9:00 - 10:30am ESTPrize-Collecting Variants11th Floor Lecture Hall 
10:30 - 11:00am ESTCoffee Break11th Floor Collaborative Space 
10:50 - 12:20pm ESTExtended Graph Problems11th Floor Lecture Hall 
12:20 - 12:25pm ESTGroup Photo11th Floor Lecture Hall 
12:25 - 1:25pm ESTLunch11th Floor Collaborative Space 
1:30 - 3:00pm ESTContest Results and Discussion11th Floor Lecture Hall