CoSy seminar: "Revisiting greedy algorithms for solving hard optimization problems"

Everyone is welcome and the first 40 people to register will be treated to a free lunch sandwich. If you do not want lunch, you are still welcome to join.

Register for a lunch sandwich (deadline: Sunday May 4).

Abstract: In this talk, we study a certain class of greedy algorithms for combinatorial optimization. Several interesting optimization methods published in recent years follow a similar "greedy" algorithmic pattern, yet their properties and optimality have generally been studied for each method in isolation. We formulate a generalized version of this algorithmic pattern, and study the properties of the solutions computed with this approach. To characterize the optimality of such solutions, we study them through the lens of so-called lexicographic max-ordering (Lex-MO) multicriteria optimization. Our key insight is that under certain conditions, the problem of finding a Lex-MO optimal solution to a multi-criteria optimization problem can be transformed into a sequence of constraint satisfaction problems. If we can solve the associated constraint satisfaction problems, we can find a Lex-MO optimal solution. By presenting a unified formulation of this class of greedy algorithms, we hope to facilitate the development of new such algorithms, and to provide a deeper understanding on the properties of existing algorithms.

This is a lecture in the seminar series held by CIM (Centre for Interdisciplinary Mathematics).