AF:Small:Geometric Embedding and Covering: Sequential and Distributed Approximation Algorithms

在过去十年中，包括蜂窝网络、无线局域网、传感器网络、社区网络等的各种无线网络已经变得无处不在。该奖项专注于其中一些网络的协议和应用程序设计所激发的算法问题。该提议试图利用的这些网络的一个特征是，网络节点通常驻留在平面或三维空间中，并且此外，这些节点的通信和感测范围也可以几何地建模（例如，作为欧几里得空间中的圆盘或球体）。因此，该奖项侧重于几何背景下的优化问题，目标是为这些问题设计算法，最终可以在网络节点上有效地实现。考虑的一类问题是几何嵌入问题，其中网络节点仅基于关于哪些其他节点在通信范围内的信息来寻求发现它们的位置。这些问题的解决方案有可能改善这些网络上的路由协议。PI考虑的另一类问题是几何覆盖问题，其目的是最佳地放置传感器节点与给定的传感能力，以覆盖某些目标区域。这种覆盖问题出现在各种传感器网络应用中，例如监控桥梁、葡萄园和工厂车间。

Over the last decade, wireless networks of various kinds, including cellular networks, wireless LANs, sensor networks, community networks, etc. have become ubiquitous. This award focuses on algorithmic problems motivated by the design of protocols and applications for some of these networks. One feature of these networks, that the proposal attempts to take advantage of, is that network nodes typically reside in the plane or in 3-dimensional space and furthermore communication and sensing ranges of these nodes may also be modeled geometrically (for example, as disks or spheres in Euclidean space). As a result the award focuses on optimization problems in the geometric context and the goal is to design algorithms for these problems that can eventually be implemented efficiently on the network nodes. One class of problems considered are geometric embedding problems in which network nodes seek to discover their locations based only on information about which other nodes are within communication range. Solutions to these problems have the potential to improve routing protocols on these networks. Another class of problems PIs consider are geometric coverage problems whose aim is to optimally place sensor nodes with given sensing abilities so as to cover certain target regions. Such coverage problems arise in a variety of sensor network applications such as monitoring bridges, vineyards, and factory floors.