CAREER: Information, Optimization and Approximation

随着过去几年数据获取能力的提高，使用这些大型数据集进行计算的挑战也增加了。在许多情况下，重复调查整个数据以回答问题正在成为一种不可行的策略。在这些情况下出现的趋势是汇总信息内容，可能会有一些损失，这样仍然可以提供合理准确的答案，但算法将只检查汇总的表示。这种方法已经在数据库查询优化器、网络监控和传感器网络中流行起来。要使上述两个阶段的战略发挥作用，总结应面向信息的最终用途。然而，在许多情况下，这两个阶段是单独调查的，它们的开发不是由最终用途指导的，而是由数学和算法的可处理性指导的。因此，得到的解远远不是最优的。这个项目的目标是研究其中几个问题的更精细的数学结构，并提供可证明的接近最优的解决方案。从智力上讲，这个项目寻求发展对几个表示问题的算法理解，这些问题产生于逼近理论和信息理论的相互作用。现有的对这些问题的分析处理通常不考虑处理不断增加的问题大小所必需的计算效率。这项研究的重点是利用组合优化技术以及采样、嵌入和近似数据结构方面的最新发展来开发有效的近似算法来解决这些问题。这些表示问题在信号处理、网络、数据库等广泛的领域中普遍存在。这些问题的有效解决方案将在监控、侦察和网络取证方面发挥重要作用，并可能影响实践。

As the capability of data acquisition has increased over the last few years, the challenges of computing with these large datasets has increased as well. In many scenarios investigating the entire data repeatedly to answer questions is becoming an infeasible strategy. The emerging trend in these contexts is to summarize the information content, perhaps with some loss, such that reasonably accurate answers can still be provided but the algorithm will only inspect the summarized representation. This approach has already gained currency in database query optimizers, network monitoring, and sensor networks. For the above two phase strategy to work the summarization should be geared towards the end use of the information. However, in many scenarios the two phases are being investigated separately and their development is not being guided by end use but by mathematical and algorithmic tractability. As a consequence the solutions obtained are far from optimal. The goal of this project is to investigate the finer mathematical structure of several of these problems and provide provably near optimal solutions.Intellectually this project seeks to develop algorithmic understanding of several representation problems that arise from the interaction of approximation theory and information theory. The existing analytical treatment of these problems, typically, does not consider computational efficiency which is necessary to cope with the ever increasing problem sizes. The focus this research is to use techniques from combinatorial optimization as well as recent developments in sampling, embeddings, and approximate data structures to develop efficient approximation algorithms for these problems. These representation problems are ubiquitous in a broad range of areas such as signal processing, networks, databases. Efficient solutions to these problems will play a significant role in monitoring, reconnaissance and network forensics and is likely to impact practice.