AF: Small: Approximation Algorithms for Graph and Combinatorial Optimization Problems

图和组合优化问题是算法开发的核心，在计算机科学和其他领域有许多应用。这两个领域的许多自然问题都是NP难的，近似算法是解决这一难题的一种非常成功的方法。除了提供算法和启发式算法外，近似还是研究NP-Hard问题结构的一个有用的透镜。尽管在逼近算法和逼近困难方面取得了巨大的进展，但一些基本的和基本的问题仍然悬而未决。这个项目将从四个广泛的领域审查几个相互关联的问题。我们的主要工具将是线性和数学规划方法，以及图论思想。问题的领域是：(I)多流和路由问题，如最大不相交路径、最大拥塞最小化和流切割间隙。中心目标是在吞吐量和并发流设置中了解分数多数据流、整数多数据流和切割之间的关系。(Ii)网络设计，特别是得到有向Steiner树问题的多对数近似，以及可生存网络设计问题的变种的可逼近性。(3)有向图中的旅行商问题(TSP)、定向运动及相关的旅行和步行问题。(4)约束和应用约束下的子模函数极大化问题。本研究涉及算法、经典组合优化、数学规划和图论。这项技术工作是为了在这些领域之间交换思想，预计它将导致基本问题的新算法和启发式方法。这些问题出现在计算机科学(特别是网络问题)、运筹学和工程学的许多应用中；这些问题将受益于算法的进步。该项目将培训两名博士生，预计将制作一份关于子模函数最大化的算法和应用的手稿。

Graphs and combinatorial optimization problems are central to algorithmic development, and have numerous applications in computer science and beyond. Many natural problems in these two areas are NP-Hard and approximation algorithms have been a very successful approach to address this intractability. In addition to providing algorithms and heuristics, approximation is a useful lens to examine the structure of NP-Hard problems. Despite the enormous progress made in the area of approximation algorithms and hardness of approximation, several basic and fundamental problems still remain wide open. This project will examine several interrelated problems from four broad areas. Our main tools will be linear and mathematical programming methods coupled with graph theoretic ideas. The problem areas of interest are:(i) Multiflow and routing problems such as maximum disjoint paths, congestion minimization and flow-cut gaps. The central goal is to understand the relationship between fractional multiflows, integer multiflows and cuts both in the throughput and concurrent flow settings. (ii) Network design, in particular obtaining a poly-logarithmic approximation for the directed Steiner tree problem, and approximability of variants of the survivable network design problem. (iii) Traveling salesman problem (TSP), orienteering and related tour and walk problems in directed graphs. (iv) Submodular function maximization subject to constraints and applications.The proposed research is at the intersection of algorithms, classical combinatorial optimization, mathematical programming, and graph theory. The technical work serves to exchange ideas between these areas and it is expected that it will lead to new algorithms and heuristics for fundamental problems. These problems arise in many applications in computer science (in particular network problems), operations research, and engineering; these would benefit from the algorithmic advances. The project will train two PhD students and a manuscript on algorithms and applications of submodular function maximization is expected to be produced.