AF: Small: Combinatorial Optimization Problems in Vertex Centric Computation

点击翻译按钮获取中文摘要

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.