Aarhus University Seal / Aarhus Universitets segl


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

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.