Approximation Algorithms for Problems of Various Complexities

本研究的目的是设计和分析逼近组合优化问题解的离散算法，由于这些问题大多是NP难的，精确解往往是不可行的；在这种情况下，近似算法是一种可行的选择。除了攻击似乎需要新策略的近似问题之外，另一个主要目标是研究为传统离散优化问题成功地发展起来的设计原理对发生在其他领域的可比较任务的适用性。在任何情况下，总是需要严格的性能分析。第一个焦点是#P-完全永久问题，它在统计物理和组合学中具有非常重要的意义。在一台并行机上，可以在确定的多项式时间内得到近似(高达一个指数因子)，甚至更快。这样的解决方案可以解决并行计算中突出的二部匹配问题。尽管匹配问题对于顺序机来说很容易，但要协调并行机上的多个处理器同时高效地工作在同一匹配上是非常困难的。还提出了用一种更传统的网络的新版本来解决并行匹配问题。该方案的另一个主题是用传统的方法来逼近NP-Hard优化问题，例如，比较方法甚至有人建议研究一些问题在P中的逼近，因为这在并行计算中可能有有趣的应用。

The purpose of this research is to design and analyze discrete algorithmsapproximating solutions to combinatorial optimization problems.Becausemany of these problems are NP-hard,an exact solution is often not feasible;in such cases approximation algorithms are a viable alternative.In additionto attacking approximation problems that seem to require new strategies,another main goal is to investigate the applicability of design principles de-veloped successfully for traditional discrete optimization problems to com-parable tasks occurring in other areas.In any ase,a rigorous performanceanalysis is always intended.A .rst focus is the #P-complete permanent problem,which is of muchimportance in statistical physics and combinatorics.Rough approximations(up to an exponential factor)can be obtained in deterministic polynomialtime and possibly even mu h faster on a parallel machine.Such a solutionwould allow to solve the outstanding bipartite matching problem of parallelcomputing.Even though the matching problem is easy for a sequentialmachine,it is very hallenging to coordinate the many processors of a parallelmachine to worksimultaneously and e .ciently on the same matching.It isalso proposed to attackthe parallel matching problem with a novel versionof more traditional network .ow methods.Another theme of this proposal is the approximation of NP-hard opti-mization problems by traditional methods like lo al search,the comparisonmethod,semide .nite optimization,or some combination of these.It is evenproposed to investigate the approximation of some problems in P,as thiscould have interesting applications in parallel computing.