Approximation Algorithms for Network Optimization

网络是全球连通性和通信进步的基础，并使现代生活的许多进步成为可能。网络优化是抽象地研究网络，提出网络建设和使用的问题。在这一领域提出的许多计算问题是难以解决的，这促使启发式近似算法的设计快速运行，并提供可证明接近最优的解决方案。该提案的关键推力是设计新的和改进的近似算法，用于基本的网络问题，包括侧约束和链接的方向性，建立在一些最近的成功。网络优化的基本问题在多项式时间内仍未得到解决，特别是具有侧约束的问题（如双准则网络设计问题）以及有向图中的问题（如有向斯坦纳树问题）。这项建议解决了这些缺点。该建议的第二个要点是利用运筹学的框架（如机会约束规划）制定新的网络优化问题。该建议的智力价值包括推动了近似算法的前沿，并为网络优化引入了新的理论模型。该提案将使研究者能够继续积极参与更广泛的教育目标，如参加邀请讲座、辅导和教学讲习班，以及新课程和讲义的开发。该提案的广泛影响包括在算法、组合学和优化等跨学科领域培养和安置非常优秀的研究生。

Networks underlie much of the progress in global connectivity and communications, and have enabled many of the advances in modern life. Network optimization studies networks in the abstract by formulating problems on the construction and usage of such networks. Many of the computational problems posed in this area are intractable motivating the design of heuristic approximation algorithms that run fast and deliver solutions that are provably near-optimal. The key thrust of the proposal is to design new and improved approximation algorithms for basic network problems incorporating side constraints and directionality of links building on some recent successes.Fundamental problems in network optimization remain unresolved in their approximation guarantee achievable in polynomial time, particularly problems with side constraints (such as bi-criterianetwork design problems) as well as those in directed graphs (such as the directed Steiner tree problem). This proposal addresses these shortcomings. A secondary thrust of this proposal is to formulate new network optimization problems drawing upon frameworks from Operations Research such as chance-constrained programming. The intellectual merit of the proposal include pushing the frontiers of approximation algorithms, and introducing new theoretical models for network optimization. The proposal will enable the continuation of the investigator's strong involvement in broader educational goals such as participation in invited talks, tutorials and teaching workshops, as well as new course and lecture note development. The broader impacts of the proposal include training and placement of very strong graduate students in the interdisciplinary areas ofalgorithms, combinatorics and optimization.