Learning When Hard Problems Are Easy

Title:

Learning When Hard Problems Are Easy

Abstract:

Many interesting and important problems, such as SAT, are known to be NP-Hard.  Nevertheless, many sophisticated algorithms have been proposed which, in practice, can provably solve some problem instances quite effectively.  Furthermore, the performance of the algorithms is often orthogonal; that is, one algorithm performs well on one set of instances, while another algorithm behaves well on a different set.  A priori, though, it is often not clear which algorithm will behave best on a given problem instance.

In this presentation, I will first introduce the algorithm selection problem [Rice, 1976], in which we aim to select the algorithm from a portfolio with the best performance on a given instance.  Next, machine learning techniques will be used to learn empirical hardness models [Leyton-Brown et al., 2002], which approximate the behavior of an algorithm on a given instance; the empirical hardness models are used to solve the algorithm selection problem.  Finally, I will describe two case studies: Bayesian network structure learning and dynamic loop scheduling.  In both cases, selecting an algorithm from the portfolio using empirical hardness models gives much better performance than using the same algorithm on all instances.

About the presenter:

Brandon Malone is a postdoctoral researcher at the University of Helsinki in the Complex Systems Computation Group. Much of his research has addressed improving the scalability of exact Bayesian network structure learning using admissible heuristic search. He has also worked with interdisciplinary groups to investigate problems in epigenetics and metagenomics. He received his PhD from Mississippi State University in 2012. Email: [email protected]