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

AF：小：图中的切割、流动和匹配问题

• 批准号: 1116961
• 负责人: Sanjeev Khanna
• 金额: $ 40万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1116961&HistoricalAwards=false
• 关键词: AF; Small; Cut; Flow; Matching

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.

该项目旨在研究有关网络中剪切、流和匹配的几个基本问​​题的计算可处理性。例如，如何设计一个最小成本网络来实现节点之间给定的一组成对连接要求？如何在网络中分配路由以避免拥塞？能够以多快的速度将任务分配给机器，以便将每项任务分配给恰好一台能够执行该任务的机器，并且不会为任何机器分配多个任务？总之，这些都是研究最广泛的组合优化问题，毫不奇怪，这些问题的研究与算法设计、近似硬度和图论的重大发展相关。该项目的目标是为这些问题和相关问题设计改进的算法，并确定为这些问题获得接近最佳解决方案的复杂性。本提案中概述的问题是许多应用程序所固有的，因此对这些问题的改进算法对于经常出现这些优化问题的计算机科学和相关学科很有价值。这里提出的研究将与教育和学生培训计划以及外展活动齐头并进。 PI 将把这项研究的主题整合到高级本科课程中，其中包括为学生提供研究机会。 PI 还将开发一系列讲座，向高中生介绍理论计算机科学中令人兴奋的想法。