Two Themes in Approximation Algorithms: Use of the Primal- Dual Schema, and Problems in Network Design

逼近算法中的两个主题：原对偶模式的使用和网络设计中的问题

• 批准号: 9627308
• 负责人: Vijay Vazirani
• 金额: $ 24万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-08-01 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9627308&HistoricalAwards=false
• 关键词: Two; Themes; Approximation; Algorithms; Use

This projects explores problems in the area of approximation algorithms, with emphasis on two themes: (1) Primal-dual schema based on approximation algorithms; and (2) Approximation algorithms for problems in network design. First, several problems are investigated that appear to have ``optimal'' approximate solutions using primal-dual schema, including generalized Steiner network problem, integral multicommodity flow and multicut in trees, the set cover problem, and the k-minimal Steiner tree problem. The second goal of the project is to provide ``good'' approximate solutions to problems, identified by AT&T Bell Labs and Bellcore, in the area of implementation and maintenance of low-cost broadband networks.***

该项目探讨了近似算法领域的问题，重点关注两个主题：（1）基于近似算法的原对偶模式； (2)网络设计问题的近似算法。 首先，研究了使用原对偶模式似乎具有“最佳”近似解的几个问题，包括广义 Steiner 网络问题、积分多商品流和树中的多重切割、集合覆盖问题和 k 最小 Steiner 树问题。 该项目的第二个目标是为 AT&T 贝尔实验室和 Bellcore 确定的低成本宽带网络实施和维护领域的问题提供“良好”的近似解决方案。***