Problems of combinatorial optimisation occur quite naturally in a diverse range of applications. They occur in
- manufacturing: how can a company improve the throughput in their manufacturing processes?
- data science: how can a large amount of data be grouped efficiently into meaningful clusters?
- scheduling: how can a personnel schedule be set up so that the largest number of constraints are satisfied?
Often, such problems turn out to hard from an algorithmic point of view: No exact efficient algorithm is known, and it's not likely that such an algorithm exist at all. These problems need to be solved nevertheless -- what can be done?
In the course, we discuss what kind of problems are hard and how to cope with them. Subjects we treat are: basic complexity theory, rounding of linear programs, randomised algorithms, clustering algorithms.
NOTE: No lecture on 16th October, first lecture on 17th