AF: Small: Geometric Clustering and Covering: New Directions

聚类是将附近的数据分组收集在一起，是数据分析中的一项关键操作，但由于有许多将数据分组的选择，其计算难度令人惊讶。本课题研究几何聚类和覆盖领域中的一些基本算法问题和新的研究方向。在这个项目中所考虑的问题的进展不仅将增强PI及其研究生的核心研究领域的知识，而且还将产生新的技术、想法和观点，这些将在核心领域之外有用。产生这种影响的途径之一是培训将从事这一项目的研究生。到他们成功完成论文时，这些学生对技术知识可能(或可能不)如何影响现实世界的问题解决有了深刻的理解，对获得可靠的新知识的难度有了认识，并对发现过程的兴奋感产生了一种感觉。在几何聚类中，目标是根据相似性将被视为一组点的数据划分为组。几何聚类可以帮助从数据中推断出有用的模式，但也可以帮助规划基础设施安装，如蜂窝网络中的基站放置。在几何覆盖中，我们希望用给定对象集的尽可能小的数目来覆盖一组点；这样的问题出现在传感器网络的环境中。本课题所研究的聚类和覆盖问题都被看作是优化问题。这些问题通常是NP完全的，这本质上意味着不可能使用保证效率的算法来精确地解决它们。PI将检验近似解决问题的有效算法，并研究可证明的最佳近似值。PI期待该项目将在近似算法和计算几何领域的交叉点上贡献令人兴奋的新想法和技术。

Clustering, which collects nearby data together in groups, is a key operation in data analysis, but one whose computation is surprisingly difficult due to the many choices for dividing data into groups. This project investigates some fundamental algorithmic problems and new directions in the areas of geometric clustering and covering. Progress on the problems considered in this project will not only enhance knowledge in the PI's core research field, and that of his graduate students, but also yield new techniques, ideas, and points of view that will be useful beyond the core area. One avenue for such impact is the training of graduate students who will work on this project. By the time they successfully complete their dissertations, these students develop a deep understanding of how technical knowledge may (or may not) influence real world problem solving, an appreciation for the difficulty of obtaining reliable new knowledge, and a sense of the excitement of the process of discovery. This experience informs their work, whether they end up in academia or industry.In geometric clustering, the goal is to partition data, viewed as a set of points, into groups based on similarity. Geometric clustering can help infer useful patterns from data, but can also help in planning infrastructure installation, such as base station placement in a cellular network. In geometric covering, we wish to cover a set of points by the smallest possible number of a given set of objects; such problems arise in the context of sensor networks. The clustering and covering problems studied in this project are viewed as optimization problems. These problems are typically NP-complete, which essentially means that it is not possible to solve them exactly using an algorithm with guaranteed efficiency. The PI will examine efficient algorithms that solve the problems approximately, and study the best approximation that can be provably guaranteed. The PI expects that the project will contribute exciting new ideas and techniques at the intersection of the fields of Approximation Algorithms and Computational Geometry.