Design and analysis of algorithms, mathematics of information retrieval, complexity theory

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

This proposal primarily concerns a number of topics relating to the design and analysis of algorithms incluing potential application to the areas of information retrieval, algorithmic mechanism design and bio- informatics. My current focus is on the design and analysis of "simple" and efficient classes of algorithms, such as greedy algorithms, local search, dynamic programming and local ratio/primal dual algorithms. These general techniques are the starting point (and sometimes the most efficient algorithms known) for many combinatorial optimization and search problems. While the meaning of such algorithmic paradigms is intuitively understood, establishing a precise and "useful" model of such algorithms is a challenging area of research. We consider precise models which capture known algorithms but moreover allow us to prove limitations on a particular approach as well as possibly suggesting ideas for deriving new algorithms.