Aarhus University Seal / Aarhus Universitets segl

MADALGO Seminar

MADALGO Theory Seminar: Edvin Berglin (MADALGO)

Info about event

Time

Wednesday 25 March 2015,  at 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.