Online and adaptive algorithms in shortest path problems, e.g., the Canadian Traveler Problem

The requirements for the above subject are given below.

There are three main ways to approach the project:

Reading project. Find a few interesting but challenging theoretical or computational papers on a coherent topic, and write up an exposition that synthesizes their ideas. You will be graded on how much clearer/more informative your exposition is than that of the original papers. While you need not give all proofs in full detail, the reader should come away with a good understanding of why it all works. Original demonstrative examples would be useful.

Theoretical research. Develop a more efficient or simpler solution method/algorithm to an interesting network flow or network optimization problem. While you will presumably need to do some background reading, there is no set lower bound on it so long as you are able to advance beyond what is known. This kind of project will be graded on the extent of the improvement on previous results.

3- Implementation project. By the end of the course, we will have studied many algorithms in theoretical form (in terms of worst-case run time), but their average behavior on different data sets can be quite surprising according to their implementation. Select a problem that interests you, implement an algorithm and test it with different data sets. You may also compare several algorithms or different mathematical formulations. This kind of project will be graded on how well you explain the algorithm or the mathematical model you are implementing, what kind of interesting heuristics you have developed, if any, what interesting test cases you ran them against, and how well you present and interpret the results. Be cautious— some implementations can take a lot of time and can be quite challenging. Working in a team will be helpful. Give serious thought to the design of the test instances—ideally, they will come from real-world problems or be generated to carry the characteristics of such problems. Alternatively, they may be specially designed to test certain strong and weak aspects of the algorithm and to show its performance according to particular problem characteristics.

Where can I find the papers? There are numerous sources of papers on algorithms and network problems. There are journals such as Networks, Operations Research, INFORMS Journal on Computing, and SIAM Journal on Computing where you can find relevant and interesting articles.