Approximation Algorithms, with an Emphasis on LP-Duality Methods

近似算法，重点是 LP 对偶方法

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

CCR-9820896VaziraniThis project pursues research in the following areas:1. The metric Steiner tree problem and its generalizations: Developing an algorithm using the bidirected cut relaxation for the metric Steiner tree problem and determining the integrality gap of this remarkable relaxation - this is widely believed to be the most promising avenue for better algorithms for this central problem. Developing a combinatorial factor 2 algorithm for the generalized Steiner network problem.2. Extending the scope of the primal-dual schema: Several problems are identified, that appear to be waiting for the "right kind" of primal-dual approach, including a facility location problem, metric TSP and integer multicommodity flow in planar graphs; besides the problems mentioned in (1) above. The RV-algorithm extends the schema in two ways: for the first time the dual growth process is not greedy, and the algorithm does not use the usual mechanism of relaxing complementary slackness conditions.3. Efficient construction of an FPRAS using an unbiased estimator: This research concerns the foundations of randomized approximation algorithms and its relationship with parametric statistical inference. Issues of computational efficiency, and a conjecture on the degree of improvement provided by a variant on the standard "median" method, are studied.4. Industry targeted implementation of Steiner tree algorithms: None of the currently known Steiner tree algorithms with proven guarantee is appropriate as the core algorithmic idea for use in the VLSI design industry. The goal is not just to present experimental evidence, but to develop, around sophisticated ideas, a package that competes with commercial Steiner tree code.5. Coding theory: Coordinate permutation can drastically reduce the size of a minimal trellis for a given code. Recently, the problem of finding the optimal permutation was shown to be NP-hard, thus partially resolving a long standing open problem. It is now important to seek good approximation algorithms.

CCR-9820896Vazirani 该项目在以下领域进行研究：1。度量斯坦纳树问题及其概括：开发一种使用度量斯坦纳树问题的双向剪切松弛的算法，并确定这种显着松弛的完整性差距 - 这被广泛认为是针对该中心问题的更好算法的最有希望的途径。 针对广义Steiner 网络问题开发组合因子2 算法。 2．扩展原对偶模式的范围：确定了几个问题，这些问题似乎正在等待“正确类型”的原对偶方法，包括设施位置问题、度量 TSP 和平面图中的整数多种商品流；除上述(1)中提到的问题外。 RV算法以两种方式扩展了该模式：第一次对偶增长过程不是贪婪的，并且该算法没有使用放松互补松弛条件的通常机制。 3．使用无偏估计器有效构建 FPRAS：这项研究涉及随机逼近算法的基础及其与参数统计推断的关系。 研究了计算效率问题以及对标准“中值”方法的变体所提供的改进程度的猜想。 4． Steiner 树算法的行业针对性实施：目前已知的具有经过验证的保证的 Steiner 树算法均不适合作为 VLSI 设计行业使用的核心算法思想。 我们的目标不仅仅是提供实验证据，而是围绕复杂的想法开发一个与商业斯坦纳树代码竞争的软件包。5。编码理论：坐标排列可以极大地减小给定代码的最小网格的大小。 最近，发现最佳排列的问题被证明是 NP 困难的，从而部分解决了一个长期存在的开放问题。 现在重要的是寻找好的近似算法。