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希望该项目将在近似算法和计算几何领域的交叉点上贡献令人兴奋的新想法和技术。