Approximation Algorithms, with an Emphasis on LP-Duality Methods

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

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.