Holger H. Hoos, University of British Columbia
Computer Science
Professor
Vancouver, British Columbia
hoos@cs.ubc.ca
Office:
(604) 822-1964
Expert In
Bio/Research
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 a...
Click to Expand >>
Click to Expand >>
Bio/Research
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.
Click to Shrink <<
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.
Click to Shrink <<