Many problems in applied computer science are naturally formulated as optimization problems. In this paradigm, we solve problems by first formulating a criterion that describes the qualities of a good solution. We then use various optimization methods to find a solution that is as good as possible according to our chosen criterion. The ubiquity of this approach to problem solving means that good optimization methods are a key enabling technology in many areas of computer science and its many applications. In this course, we will study combinatorial optimization problems, which are discrete optimization problems with a finite (but usually still very large) number of solutions. Specifically, we will study such optimization problems formulated on graphs. Finding a globally optimal solution to such optimization problems is a challenging computational task – many problems in this area are known to be NP-hard. There are, however, restricted classes of such problems for which efficient algorithms can be formulated. In many cases, these algorithms are guaranteed to produce globally optimal solutions in low-order polynomial time. In other cases, they can be used to produce approximate solutions, with strong guarantees on local optimality. Throughout the course, applications from image analysis and computer vision are used as motivating examples, but the methods studied in the course are fairly general and should be of interest to a more general audience in computer science and applied mathematics.
To sign up for the course, send an email to Filip Malmberg.
Ph.D. students who complete the course recieve 5 hp.