11th DIMACS Implementation Challenge


Workshop

The Challenge workshop will be hosted by ICERM (in Providence, Rhode Island) on December 4-5, 2014. More details on the workshop will be posted here as they become available. Make sure to join the mailing list to receive news.

Note that works presented at the workshop are not refereed. Some unpublished papers presented at the workshop will be invited to submit to a special issue of Mathematical Programming Computation, at which point they will be subject to the standard revewing process. The workshop itself does not have proceedings. For convenience to the attendees, however, this page will soon include links to relevant papers (published or to be published elsewhere, or available as technical reports).

Program

Thursday (Dec 4)

8:15 - 8:40

Registration and Breakfast (provided)

8:40 - 9:00

Opening Remarks

DIMACS Implementation Challenges: Past, Present, and Future
David S. Johnson

9:00 - 10:30

Classical Steiner Problem in Graphs

Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks
Krzysztof Ciebiera, Piotr Sankowski, Piotr Godlewski and Piotr Wygocki

A Robust and Scalable Algorithm for the Steiner Problem in Graphs
Thomas Pajor, Eduardo Uchoa and Renato Werneck

Dijkstra meets Steiner: Computational results of a fast exact Steiner tree algorithm
Stefan Hougardy, Jannik Silvanus and Jens Vygen

10:30 - 10:50

Coffee break

10:50 - 12:20

Flexible Techniques

SCIP-Jack – A solver for STP and variants with parallelization extensions
Gerald Gamrath, Thorsten Koch, Stephen J. Maher, Daniel Rehfeldt and Yuji Shinano

Thinning out Steiner trees: A node-based model for uniform edge costs
Matteo Fischetti, Markus Leitner, Ivana Ljubic, Martin Luipersbeck, Michele Monaci, Max Resch, Domenico Salvagnin and Markus Sinnl

On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
Indaco Biazzo, Anna Muntoni, Alfredo Braunstein and Riccardo Zecchina

12:20 - 14:00

Lunch (provided)

14:00 - 15:30

Euclidean and Rectilinear Variants

Faster Exact Algorithms for Computing Steiner Trees in Higher Dimensional Euclidean Spaces
Rasmus Fonseca, Marcus Brazil, Pawel Winter and Martin Zachariasen

Steiner Tree Heuristics in Euclidean d-Space
Andreas E. Olsen, Stephan S. Lorenzen, Rasmus Fonseca and Pawel Winter

The GeoSteiner Software Package for Computing Steiner Trees in the Plane: An Updated Computational Study
Daniel Juhl, David M. Warme, Pawel Winter and Martin Zachariasen

15:30 - 16:00

Coffee break

16:00 - 17:30

Constrained Variants

A Fast Algorithm for Rectilinear Steiner Trees with Length Restrictions on Obstacles
Stephan Held and Sophie Spirkl

Local Search Heuristics for Hop-constrained Directed Steiner Tree Problem
Oleg Burdakov, Jonas Kvarnstrom and Patrick Doherty

A New Layered Graph Approach to Hop- and Diameter-constrained Spanning/Steiner Tree Problems in Graphs
Markus Sinnl and Ivana Ljubic

18:00

Reception



Friday (Dec 5)

8:30 - 9:00

Breakfast (provided)

9:00 - 10:30

Prize-Collecting Variants

Knowledge Guided Tabu Search for the Prize Collecting Steiner Tree Problem in Graphs
Zhanghua Fu and Jin-Kao Hao

A Fast, Adaptive Variant of the Goemans-Williamson Scheme for the Prize-Collecting Steiner Tree Problem
Chinmay Hegde, Piotr Indyk and Ludwig Schmidt

Algorithms for the Maximum Weight Connected Subgraph and Prize-collecting Steiner Tree Problems
Ernst Althaus and Markus Blumenstock

10:30 - 10:50

Coffee break

10:50 - 12:20

Extended Graph Problems

Solving the Maximum-Weight Connected Subgraph Problem to Optimality
Mohammed El-Kebir and Gunnar W. Klau

Generalized local branching heuristics and the capacitated ring tree problem
Alessandro Hill and Stefan Voss

A Heuristic Approach for the Stochastic Steiner Tree Problem
Pedro Hokama, Mario Cesar San Felice, Evandro Cesar Bracht and Fabio Luiz Usberti

12:20 - 13:30

Lunch (provided)

13:30 - 15:00

Contest Results and Discussion

15:00

Workshop adjourns


Registration, Travel, and Support

At least one author of each paper is expected to attend the workshop. Registration is now open: http://dimacs.rutgers.edu/Workshops/Challenges11/

ICERM and DIMACS will be able to provide some travel support to participants, in the shape of registration fee waivers, hotel reimbursement (at the workshop hotel), and/or partial reimbursement of air travel. If you would like to be considered for travel support, please let the organizers know. Note that funds are limited, and we will not be able to provide full support to everyone.

ICERM has reserved a block of rooms at deeply discounted rates at the Hampton Inn & Suites Providence Downtown, which is within walking distance. Workshop partcipants may book through this link. Book by November 12 to get the discounted rate. (If you plan to arrive before December 3 or leave after December 6, please contact the organizers; we will try to work with ICERM to get the discounted rate for the additional days.)

Please be aware that reimbursement of air travel requires generally requires using a US flag carrier, but there may be exceptions involving flag carriers from the European Union and some other places. Before booking your flight, you should contact the DIMACS Financial Assistant to make sure it would be eligible for reimbursement. Additional information about travel support can be found at the DIMACS website.

Note that flights to Providence Airport may be significantly more expensive than those to Boston (a 50-minute train ride away) or New York City (a 3-hour train ride away). If you decide to use these alternatives, make sure to print an alternative itinerary (going straight to Providence) as proof that your choice was indeed cheaper.