Approximation Algorithms, with an Emphasis on LP-Duality Methods

CCR-9820896Vazirani这个项目在以下方面进行了研究：1.度量Steiner树问题及其推广：为度量Steiner树问题开发了一个使用双向割松弛的算法，并确定了这种显着松弛的完整性缺口-这被广泛认为是解决这个中心问题的更好算法的最有前途的途径。提出了求解广义Steiner网络问题的组合因子2算法。扩展原始-对偶模式的范围：确定了几个问题，这些问题似乎正在等待原始-对偶方法的“正确类型”，包括设施选址问题、度量TSP和平面图中的整数多商品流；以及上面(1)中提到的问题。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.