Seminar cancelled
- Date
- 12 October 2026, 14:15–15:00
- Location
- Theatrum Visuale, room 100155, building 10, Ångström Laboratory
- Type
- Seminar
- Lecturer
- Zoe Dumoulin
- Organiser
- Centre for Image Analysis
- Contact person
- Natasa Sladoje
Today's seminar is cancelled!
A general algorithmic pattern for finding lexicographic max-ordering solutions to combinatorial multicriteria optimization problem – Zoe Dumoulin
We hope to have it at a later time.
We study a particular class of greedy algorithms for combinatorial optimization problems, and present a generalized version of this algorithmic pattern encompassing several previously published algorithms. We analyze the properties of the solutions produced by such algorithms, and provide proofs of their optimality through the concept of lexicographic max-ordering. A lexicographic max-ordering solution is both max-ordering and pareto optimal, and is an alternative way of defining optimality of multicriteria problems that was proposed by Erghott1.
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 ones. To illustrate the utility of our results we present two case studies, the Correlation clustering and the Binary graph labeling, where we study two previously published optimization algorithms, the mutex watershed algorithm and the Malmberg-Ciesielski algorithm, and show that they can be seen as instances of the proposed general algorithmic pattern. In doing so, we provide alternative proofs of correctness for these algorithms and draw new conclusions about their properties.
1 Ehrgott, M.: Lexicographic max-ordering – a solution concept for multicriteria combinatorial optimization (1995)

Speaker: Zoe Dumoulin