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

算法设计与分析、信息检索数学、复杂性理论

• 批准号: 7631-2007
• 负责人: Borodin, Allan
• 金额: $ 5.39万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=450136
• 关键词: Design; analysis; algorithms; mathematics; information

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.

该建议主要涉及与算法的设计和分析有关的一些主题，包括在信息检索、算法机制设计和生物信息学领域的潜在应用。我目前的重点是设计和分析“简单”和有效的算法，如贪婪算法，局部搜索，动态规划和局部比率/原始对偶算法。这些通用技术是许多组合优化和搜索问题的起点（有时是已知的最有效的算法）。虽然这种算法范例的含义是直观理解的，但建立这种算法的精确和“有用”的模型是一个具有挑战性的研究领域。我们认为精确的模型，捕捉已知的算法，而且让我们证明一个特定的方法的限制，以及可能提出的想法，推导出新的算法。