Workshop in algorithms and data structures, 2006

(0368-3500-37)

Lecturer:	Prof. Haim Kaplan (Sunday, 13:00-15:00, Shreiber 007)
Tel:	8814
E-mail:	haimk@post.tau.ac.il
T.A.:	Svetlana Olonetsky
E-mail:	olonetsk@post.tau.ac.il

General

• The project will be done in groups of 2-3 students.
• You have to implement few variations of an algorithm or different algorithms and compare their performance on some graph classes. You can redo a comparison which has been published (possibly with a new twist on it) or make up your own new comparison. Your benchmark would be interesting if its results are not easy to predict. You need to give special notice of the followings:
• Which problem do you study and which algorithms you implement
• Which graphs classes you are going to use, how do you generate them or where do you get them from.
• Which performance measures of the algorithms you compare. Sometimes you could use other measures than “running time” or ”memory usage”. These may depend on the algorithm (like the # of vertices “scanned” if you work on shortest paths), or measures like cache performance.
• Language, library, and platform

Requirements

• A specification document should be submitted until 01/04/2008
• It should include the followings:

• A detailed description of the algorithms and data structures that you implement
• Which graphs you’d run on
• What is the purpose of your project, why the comparison you make is interesting?
• Environment: programming language, libraries you use, etc.
• Description of the user interface. (inputs, outputs, etc.)
• A birds-eye view on the design of the project: Major procedures, etc.
• Testing plan: How correctness and efficiency will be proven.

· A significant task will be to make the program easy to check. It should be comprehensible; well-documented; and partitioned into logical components such that each can be tested by itself.

Important dates

· Project submission: 25/09/2008.

· Submission of specification document is: 01/04/2008

Lecture notes: (ppt)

Possible Topics:

Some of the links point to theoretical papers that develop various algorithms, other point to previous experimental studies. The list of references is not comprehensive.

• Single source shortest paths
1. A Practical Shortest Path Algorithm with Linear Expected Time by A. V. Goldberg, to appear in SIAM Journal on Computing
2. Implementations of Dijkstra's Algorithm Based on Multi-Level Buckets by A. V. Goldberg and C. Silverstein
• All pairs shortest paths
• k shortest paths (simple and not simple)
1. Replacement paths and k simple shortest paths in unweighted directed graphs by Liam Roditty,Uri Zwick
2. Finding the k Shortest Simple Paths: A New Algorithm and its Implementation by John Hershberger, Matthew Maxel and Subhash Suri.
3. Finding the k shortest paths by David Eppstein
4. k Shortest Path Algorithms by José L. Santos
5. Implementations and Empirical Comparison of K Shortest Loopless Path Algorithms
   by Marta M. B. Pascoal
• Spanners/Distance oracle
1. Deterministic Constructions of Approximate Distance Oracles and Spanners by Liam Roditty, Mikkel Thorup and Uri Zwick
2. Approximate Distance Oracles by Mikkel Thorup and Uri Zwick
3. Approximate Distance oracles for Unweighted Graphs in Expected O(n^2) Time by John Surender Baswana and Sandeep Sen
• Point-to-point shortest path
1. Better Landmarks within Reach by Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck
2. In Transit to Constant Time Shortest-Path Queries in Road Networks by Holger Bast, Stefan Funke, Domagoj Matijevic, Peter Sanders, Dominik Schultes
• Maximum flow
1. On Implementing Push-Relabel Method for the Maximum Flow Problem by B. V. Cherkassky and A. V. Goldberg
• Minimum cost flow
1. An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm by A. V. Goldberg
2. Efficient implementation of the goldberg-tarjan minimum cost flow algorithm by U. BÜNNAGEL, B. KORTE, and J. VYGEN.
3. Solving Large-Scale Real-World Minimum-Cost Flow Problems by a Network Simplex Method by Andreas Löbel
• Matching/Assignment

Algorithm engineering

There has been a lot of research in the last 10 years or so on how to efficiently implement various algorithms, as well as empirical comparisons between them. This is in order to bridge the gap between the theoretical algorithmic community and engineers.

By now there are three yearly international conferences on algorithm engineering:

1) Workshop on Algorithm Engineering (WAE)

2) ALENEX

3) ESA (track B)

You can get a lot of material and ideas by looking at the papers which were published in these conferences. Most of the material can be accessed online with a TAU IP address.

Graph resources

^{9th Dimacs implementation challenge on shortest paths}

Presentations