AF: Small: Geometric Clustering and Covering: New Directions

AF：小：几何聚类和覆盖：新方向

• 批准号: 1615845
• 负责人: Kasturi Varadarajan
• 金额: $ 39.97万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-01 至 2022-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1615845&HistoricalAwards=false
• 关键词: AF; Small; Geometric; Clustering; Covering

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.

聚类将附近的数据组合在一起，是数据分析中的关键操作，但是由于将数据分组分为组的许多选择，其计算非常困难。该项目研究了几何聚类和覆盖领域的一些基本算法问题和新方向。该项目中考虑的问题的进展不仅将增强PI核心研究领域的知识，以及他的研究生的知识，而且还会产生新的技术，想法和观点，这些技术，思想和观点将在核心领域之外有用。产生这种影响的途径是培训将在该项目中工作的研究生。当他们成功完成论文时，这些学生对技术知识可能（或可能不会）如何影响现实世界问题解决，对获得可靠的新知识的困难的欣赏以及对发现过程的兴奋感的欣赏。这种经验为他们的工作提供了信息，无论他们最终都进入学术界还是行业。在几何聚类中，目标是根据相似性将数据（视为一组要点）分组分组。几何聚类可以帮助从数据中推断出有用的模式，但也可以帮助计划基础设施安装，例如蜂窝网络中的基站放置。在几何覆盖物中，我们希望通过一组给定的对象数量的最小数量覆盖一组点；这些问题在传感器网络的背景下出现。该项目研究的聚类和涵盖问题被视为优化问题。这些问题通常是NP完整的，这实际上意味着无法使用具有保证效率的算法来精确地解决它们。 PI将检查有效解决问题的有效算法，并研究可以保证的最佳近似值。 PI预计该项目将在近似算法和计算几何学领域的交集中贡献令人兴奋的新思想和技术。