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