Research in Algorithms Complexity and Database Theory

PI和他的合作者参与了：（a）一些最近取得了令人印象深刻的进展的理论子领域（近似算法，在线算法），（B）一个非常成功和相关的子领域，但面临着新的挑战（数据库理论），以及（c）向其他学科“出口”复杂性理论思想（例如，博弈论、经济学和人工智能）。 该项目的目标包括：（1）通过解决欧几里德旅行商问题和k-服务器猜想等基本问题，深化和拓宽近似算法和在线算法的最新进展;（2）对替代模型和度量的研究，例如，关于存储分配的在线算法，（3）引入近似和在线问题，这在一定程度上有助于我们理解全球信息环境的计算要求;（4）研究新媒体和异构性带来的数据库理论问题;（5）继续PI的研究计划，考虑其他学科的问题（如博弈论，遗传学和人工智能）从复杂性理论的角度来看。

The PI and his collaborators have been involved in: (a) some of the subfields of theory that have witnessed impressive recent advances (approximation algorithms, on-line algorithms), (b) a subfield that has been very successful and relevant, but is facing new challenges (database theory), and(c) ``exporting'' complexity-theoretic ideas to other disciplines (e.g., Game Theory, Economics, and Artificial Intelligence). The goals of this project include: (1) The deepening and broadening of recent advances in approximation algorithms and on-line algorithms, by attacking fundamental problems such as the Euclidean traveling salesman problem and the k-server conjecture; (2) The study of alternative models and metrics, for example, in relation to on-line algorithms for storage allocation, that are closer to reality and to computational practice; (3) The introduction of approximation and on-line problems that in a small way contribute to our understanding of the computational requirements of a global information environment; (4) The study of database-theoretic problems that are posed by novel media and heterogeneity; (5) The continuation of PI's research program that considers problems from other disciplines (such as, Game Theory, Genetics, and Artificial Intelligence) from a complexity-theoretic point of view.***