HIIT seminars in fall 2007 will be held in hall **B222** of Exactum, on Fridays starting at 10:15 a.m. Coffee available from 10.
Fri Oct 12
Dr. Thore Husfeldt
Computer Science Department, Lund University
Inclusion-exclusion in combinatorial optimisation
Abstract:
I present the well-known principle of inclusion-exclusion and survey its applications to algorithms, namely to combinatorial optimisation. This includes classical results like Ryser's formula for the permanent, forgotten results for the Hamiltonian cycles, and recent results on partitioning and subset convolution, presented within the framework of partial order theory. The amibition is to make the presentation self-contained and accessible to an audience encumbered by not much more than an introductory algorithms class and some discrete maths.
Last updated on 23 Oct 2007 by Teija Kujala - Page created on 12 Oct 2007 by Teija Kujala