Holger H. Hoos
M.Sc., Darmstadt University of Technology (1996); Ph.D., Darmstadt University of Technology (1998); Postdoctoral Fellow, University of British Columbia (1998-2000); Assistant Professor, University of British Columbia (2000-2005); Associate Professor, University of British Columbia (2005-2010); Professor, University of British Columbia (since 2010).
Hard combinatorial problems occur in many areas of computer science and its applications, such as Artificial Intelligence, Bioinformatics, and Electronic Commerce. Although theoretical complexity results suggest that most of these problems are exponentially hard in the worst-case, this does not always mean that they cannot be solved reasonably effectively in practice. One of my primary research interests is to study hard combinatorial problems, and to explore algorithmic ways of solving them as efficiently as possible in practical applications.
In this context, I am particularly interested in stochastic search algorithms that combine goal-directed, greedy search with randomised decisions. This group of algorithms includes general algorithmic techniques such as simulated annealing, evolutionary algorithms, ant-colony optimisation, or stochastic hill-climbing, as well as problem-specific algorithms. I have been working on various types of stochastic local search algorithms, investigated and modelled their behaviour, and developed new, improved algorithms for various applications, such as the satisfiability in propositional logic (SAT), the travelling salesperson problem (TSP), or winner-determination in combinatorial auctions. Currently, I am particularly interested in studying and developing stochastic search techniques for problems in bioinformatics, biocomputing, artificial intelligence, and electronic commerce.
Although stochastic search algorithms are typically rather easy to implement, their behaviour is quite complex and presently not well understood. Much like other, more complex systems or algorithms, they are difficult to analyse theoretically. Therefore, empirical methodology is crucial for analysing and improving these algorithms. Compared to the methods used in other sciences, such as physics or biology, the empirical methodology for studying algorithms or systems in computer science is quite underdeveloped. I am working on improved methods for the empirical analysis of algorithms and use these methods for studying stochastic search algorithms. Such advanced empirical methods allow me to investigate and to model aspects of these algorithms' behaviour that are often not accessible to theoretical analysis. The potential of this approach is illustrated by recent breakthroughs in the development and application of algorithms for hard combinatorial problems that have been substantially facilitated by advanced empirical methodology.
Computer Music is an exciting interdisciplinary field that combines artistic and scientific approaches and considerations; it has also strong links to fundamental issues in artificial intelligence and human-computer interaction. My work in Computer Music is focussed on software environments for the computer-assisted generation, manipulation, and analysis of score-level musical material as well as on the symbolic representations that provide the basis for such systems.
Programming by Optimization. Holger H. Hoos - Communications of the ACM 55(2):70-80, February 2012.
Stochastic Local Search: Foundations and Applications. Holger H. Hoos and Thomas Stutzle - Morgan Kaufmann, San Francisco (CA), USA, 2004.
Boosting Verification by Automatic Tuning of Decision Procedures. Frank Hutter, Domagoj Babic, Holger H. Hoos and Alan Hu - Proceedings of the 7th International Conference on Formal Methods in Computer-Aided Design (FMCAD-07), pp. 27-34, 2007.
SATzilla: Portfolio-based Algorithm Selection for SAT. Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown - Journal of Artificial Intelligence Research, Volume 32, pp. 565–606, 2008.
Computational approaches for RNA energy parameter estimation. Mirela Andronescu, Anne Condon, Holger Hoos, David Mathews and Kevin Murphy - RNA 16(12): 2304-2318, 2010.
Representing Score-Level Music Using the GUIDO Music-Notation Format. Holger H. Hoos, Keith A. Hamel, Kai Renz, and Jurgen Kilian - Computing in Musicology, Vol 12, MIT Press, 2001.
Solving Combinatorial Auctions using Stochastic Local Search. Holger H. Hoos and Craig Boutilier - Proceedings of AAAI-2000, pp. 22-29, MIT Press, 2000.