AF: Small: Combinatorial Optimization Problems in Vertex Centric Computation

以顶点为中心的模型，如LOCAL模型和CONGEST模型，是突出的分布式模型，它们捕捉设备如何在不访问全局信息的情况下协调计算。这些模型封装了各种分布式场景中产生的计算，包括传感器网络、机器人、无线网络和生物代理网络。组合优化是研究寻找一种使某些目标最优的对象排列方式。许多组合优化问题可以在传统的集中式环境下有效地解决，而以分布式顶点为中心的算法的进展却远远落后。本项目旨在为几个以顶点为中心模型的基本组合优化问题开发新的算法。高效的以顶点为中心的算法的发展将促进计算范式向高度分布式系统的转变。他们还将加强蜂群机器人、自动驾驶汽车、无人驾驶飞行器等自主系统的技术。此外，在模型中开发的算法可以直接转换为使用现有框架（如Apache GraphX）在现代架构中处理大量图形的算法。为了推广以顶点为中心的模型，该项目包括在波士顿学院开发一门新课程，将模型的理论和实践方面结合起来。该项目将重点关注以下三个基本的组合优化问题：(i)匹配，即匹配实体，使总效用最大化或最小化；（ii）路由，即在尽量减少拥塞和延迟的情况下，同时将多个消息从其来源路由到其目的地；（iii）聚类，即根据节点之间的相关性对节点进行尽可能一致的划分。该项目的目标是开发新的以顶点为中心的算法，以尽可能快地计算答案，同时使答案尽可能接近最优。实现这样的目标需要建立新的工具和技术，这将导致对如何在顶点中心模型中解决更广泛的组合优化问题有更深的理解。此外，由于在以顶点为中心的模型中开发的技术通常需要开发轻量级流程和利用并行性，因此它们通常可以应用于其他计算模型，如流模型、动态图模型、局部计算模型和大规模并行计算模型。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Vertex-centric models, such as the LOCAL model and the CONGEST model, are prominent distributed models that capture how devices coordinate computation without access to global information. Such models encapsulate the computation arising in various distributed scenarios, including sensor networks, robotics, wireless networks, and networks of biological agents. Combinatorial optimization is a study of finding an arrangement of objects that optimizes certain objectives. While many combinatorial-optimization problems can be solved efficiently in the traditional centralized setting, progress on distributed vertex-centric algorithms is largely falling behind. This project aims to develop new algorithms for several fundamental combinatorial-optimization problems in vertex-centric models. Developments in efficient vertex-centric algorithms will facilitate the shifting of computing paradigms into highly distributed systems. They will also enhance the technologies for autonomous systems such as swarm robotics, self-driving cars, and unmanned aerial vehicles. Moreover, algorithms developed in the models can be directly transformed into algorithms for processing massive graphs in modern architectures using existing frameworks such as Apache GraphX. To promote the vertex-centric models, the project includes the development of a new course at Boston College that integrates the theoretical and practical aspects of the models. The project will focus on the following three basic combinatorial-optimization problems: (i) matching, which is to match up the entities so that the total utility is maximized or minimized; (ii) routing, which is to route multiple messages simultaneously from their sources to their destinations while minimizing congestion and the delay; (iii) clustering, which is to partition the nodes as consistently as possible with the correlation among the nodes. The goals of the project are to develop new vertex-centric algorithms that compute the answers as fast as possible while keeping the answers as close to the optimal as possible. Achieving such goals involves establishing new tools and techniques, which would lead to a deeper understanding of how to solve a wider range of combinatorial optimization problems in the vertex centric models. Also, as the techniques developed in the vertex-centric models usually require the development of lightweight processes and exploitation of parallelism, they can often be applied to other computational models such as streaming models, dynamic graph models, local computation models, and massively parallel computation models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.