Research on Algorithms, Complexity, and Database Theory

算法、复杂性和数据库理论研究

• 批准号: 9820897
• 负责人: Christos Papadimitriou
• 金额: $ 40.04万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-15 至 2003-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9820897&HistoricalAwards=false
• 关键词: Research; Algorithms; Complexity; Database; Theory

CCR-9820897PapadimitriouAbstract:This project concerns research on algorithms, complexity, and their applications to database theory, economics and organization theory, and the life sciences. In database theory it explores the indexability of database workloads, the applicability of spectral methods to information retrieval problems, new concepts and techniques in data mining, and novel languages for topological queries. In applications, it investigates a novel model of organizations as information expediters; algorithmic questions that arise in relation to resource sharing and the information economy; the complexity of inferring the genetic basis of multigenic traits; as well as certain algorithmic problems arising in the modeling and analysis of cancer progress and protein folding. In the core theory of algorithms and complexity, it investigates output-polynomial algorithms circuit minimization, and approximate algorithms for the traveling salesman problem.

CCR-9820897Papadimitriou摘要：该项目涉及算法、复杂性及其在数据库理论、经济学和组织理论以及生命科学中的应用的研究。 在数据库理论中，它探讨了数据库工作负载的可索引性、谱方法在信息检索问题中的适用性、数据挖掘中的新概念和技术以及拓扑查询的新语言。 在应用中，它研究了一种作为信息促进者的新型组织模型；与资源共享和信息经济相关的算法问题；推断多基因性状遗传基础的复杂性；以及癌症进展和蛋白质折叠建模和分析中出现的某些算法问题。 在算法和复杂性的核心理论中，它研究了输出多项式算法电路最小化以及旅行商问题的近似算法。