Aarhus University Seal / Aarhus Universitets segl


MADALGO Theory Seminar: Edvin Berglin (MADALGO)

Info about event


Wednesday 25 March 2015,  at 14:15 - 15:00


Building 5335, Nygaard-395

Improving your exponents with Measure and conquer

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.