AF: Small: Cut, Flow, and Matching Problems in Graphs

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

This project aims to study computational tractability of several fundamental problems concerning cuts, flows, and matchings in networks. For instance, how does one design a minimum cost network that realizes a given set of pair-wise connectivity requirements among the nodes? How does one assign routes in a network so as to avoid congestion? How fast can one find an assignment of tasks to machines so that each task is assigned to exactly one machine capable of executing the task and no machine is given more than one task? Together, these are among the most widely studied combinatorial optimization problems, and it is no surprise that the study of these problems is connected to major developments in algorithms design, hardness of approximation, and graph theory. The goal of this project is to design improved algorithms for these and related problems as well as to identify the complexity of obtaining near-optimal solutions for them.The problems outlined in this proposal are intrinsic to many applications, and thus improved algorithms for these problems are of value to computer science and related disciplines where these optimization problems routinely arise. The research proposed here will go hand-in-hand with educational and student-training initiatives as well as outreach activities. The PI will integrate topics from this research in an advanced undergraduate course that will include research opportunities for students. The PI will also develop a lecture series to introduce high school students to exciting ideas in theoretical computer science.