Optimization 2

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.

Language: English

NOTE: No lecture on 16th October, first lecture on 17th