AF: Small: Combinatorial Optimization Problems in Vertex Centric Computation

AF：小：顶点中心计算中的组合优化问题

• 批准号: 2008422
• 负责人: Hsin-Hao Su
• 金额: $ 45万
• 依托单位: Boston College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008422&HistoricalAwards=false
• 关键词: AF; Small; Combinatorial; Optimization; Problems

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.

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

项目成果

Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence

最长递增子序列的近最优并行算法

• DOI: 10.1145/3558481.3591078
• 发表时间: 2023
• 期刊: ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Cao, Nairen;Huang, Shang-En;Su, Hsin-Hao
• 通讯作者: Su, Hsin-Hao

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition

论纳什-威廉姆斯森林分解和星形森林分解的局部性

• DOI: 10.1137/21m1434441
• 发表时间: 2023
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Harris, David G.;Su, Hsin-Hao;Vu, Hoa T.
• 通讯作者: Vu, Hoa T.

Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions

通过扩展器分解缩小稀疏网络中的局部拥塞差距

• DOI: 10.1145/3519270.3538423
• 发表时间: 2022
• 期刊: ACM Symposium on Principles of Distributed Computing
• 作者: Chang, Yi-Jun;Su, Hsin-Hao
• 通讯作者: Su, Hsin-Hao

Distributed Dense Subgraph Detection and Low Outdegree Orientation

• DOI: 10.4230/lipics.disc.2020.15
• 发表时间: 2019-07
• 期刊: ArXiv
• 作者: Hsin-Hao Su;H. Vu

(1-eps)-Approximate Maximum Weighted Matching in poly(1/eps, log n) Time in the Distributed and Parallel Settings

(1-eps)-分布式和并行设置中 Poly(1/eps, log n) 时间的近似最大加权匹配

• DOI: 10.1145/3583668.3594570
• 发表时间: 2023
• 期刊: ACM Symposium on Principles of Distributed Computing
• 作者: Huang, Shang-En;Su, Hsin-Hao
• 通讯作者: Su, Hsin-Hao