Approximation Algorithms for Network Optimization

网络优化的近似算法

• 批准号: 0728841
• 负责人: Ramamoorthi Ravi
• 金额: $ 25.13万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728841&HistoricalAwards=false
• 关键词: Approximation; Algorithms; 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.

网络是全球连通性和通信进步的基础，并使现代生活的许多进步成为可能。网络优化研究网络在抽象的制定问题的建设和使用这样的网络。 在这一领域提出的许多计算问题是棘手的激励设计的启发式近似算法，运行速度快，并提供可证明接近最优的解决方案。该提案的主要目的是在最近的一些成功的基础上，为基本网络问题设计新的和改进的近似算法，其中包括边约束和链路方向性。网络优化中的基本问题仍然没有解决，因为它们的近似保证在多项式时间内可以实现，特别是边约束问题（如双准则网络设计问题）以及有向图中的问题（如有向Steiner树问题）。这项建议解决了这些缺点。这个建议的第二个重点是制定新的网络优化问题，借鉴运筹学的框架，如机会约束规划。该提案的智力价值包括推动近似算法的前沿，并为网络优化引入新的理论模型。该提案将使调查员能够继续积极参与更广泛的教育目标，例如参加邀请的讲座，辅导和教学研讨会，以及新课程和演讲稿的编写。该提案的更广泛的影响包括在算法，组合学和优化的跨学科领域非常强大的研究生的培训和安置。