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

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

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.***