Project

In the project, you will work together in teams of 2 on a board game inspired problem. The possible settings can be found here. Each team will be given a different setting based on preferences they submit (details to follow). Your tasks are:

1. Formally define your problem and possibly variants (including parameterizations) of it and write an ILP model for it. See here for details.
2. Develop an initial algorithm based on Branch-and-Bound. It should be a correct and sensible algorithm, but formal guarantees on running time, etc. are not required. See here for details.
3. Evaluate the complexity of your problem and variants, by showing NP-hardness and possibly hardness with respect to some parameters.
4. Choice between: (a) Establish some non-trivial theoretical result for your problem, for example FPT algorithm with respect to some parameters (b) implement an algorithmic idea and run experiments

Remarks:

• some of the problems are more complicated than others. You are free to make simplifying assumptions, for example, removing some constraints from the problem.
• start with the easiest, not the most complicated techniques from the course. Similarly, start by simplifying the problem as much as you can, to obtain initial ideas that might transfer to more general variants.
• Goals: nice ideas, efficiency, generality of the algorithm (priority in this order)
• These are difficult projects. I do not know the outcome of them. It is expected that you run into obstacles or get stuck at some point. Do not give up easily!
• More to come

Links

• Project settings
• Task 1
• Task 2