Aarhus University Seal / Aarhus Universitets segl

MADALGO Seminar

MADALGO Theory Seminar: Edvin Berglin (MADALGO)

2015.03.18 | Katrine Østerlund Rasmussen

Date Wed 25 Mar
Time 14:15 15:00
Location Building 5335, Nygaard-395

Title
Improving your exponents with Measure and conquer


Abstract
Branch-and-reduce is a common strategy for finding exact solutions to NP-complete problems. For decades, such algorithms got more complex while the analyses thereof remained simple. I present the "measure and conquer" technique, enabling refined analysis through the insight that not all parts of the input contribute equally to its complexity. Applied to two simple algorithms -- for minimum dominating set and minimum independent set -- we drastically improve on, resp. become competitive with, the leading algorithm.


Work is done by Fedor Fomin, Fabrizio Grandoni and Dieter Kratsch.