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