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.

本计画旨在研究网路中切割、流与匹配等基本问题的计算易处理性。例如，如何设计一个最小成本的网络，实现一组给定的成对连接的节点之间的要求？如何在网络中分配路由以避免拥塞？一个人能多快找到一个任务分配给机器，使得每个任务被分配给一台能够执行该任务的机器，而没有机器被分配一个以上的任务？总之，这些都是最广泛研究的组合优化问题，这是毫不奇怪的，这些问题的研究是连接到算法设计，近似硬度和图论的主要发展。这个项目的目标是设计改进的算法，这些和相关的问题，以及确定获得接近最优的解决方案，为them.The问题的复杂性，在这个建议中列出的是固有的许多应用程序，因此，这些问题的改进算法是有价值的计算机科学和相关学科，这些优化问题经常出现。这里提议的研究将与教育和学生培训倡议以及推广活动齐头并进。PI将从这项研究中整合主题，在一个先进的本科课程，将包括学生的研究机会。PI还将开发一系列讲座，向高中生介绍理论计算机科学中令人兴奋的想法。