Probabilistic Considerations in the Analysis of Algorithms

点击翻译按钮获取中文摘要

The investigator will continue his work on the interplay betweenprobability and algorithms. He has identified two distinct but very important aspects of such study. In the first instance he will study randomized algorithms i.e. those algorithms that introduce randomnessas a means of speeding up computation. In the second instance, he will consider the average case performance of algorithms. Here, he wants to tryto explain the good performance of simple algorithms on "typical" problems as opposed to the worst-case performance exemplified by the pathological examples of complexity theory.In the area of randomized algorithms, the investigator will considerproblems arising in the study of Monte Carlo Markov Chain algorithms.In particular he will study their use in problems associated with combinatorial counting problems and with problems in Statistical Physics. He will also continue his study of the Edge Disjoint Path problem and the construction of a generalisation of the well knownmatrix Singular Value Decomposition to multi-dimensional matrices. In the area of average case analysis, he will continue his work on theTraveling Salesman Problem and try to extend his ideas to the independent symmetric model. He will continue his work on analysing the efficacy of the Sequencing By Hybridization technique in ComputationalBiology. Finally, he will continue to work on probabilistic models of theWorld Wide Web in an attempt to find a useful model for the testing of algorithmic ideas.