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.