Approximation Algorithms for Problems of Various Complexities

本研究的目的是设计和分析组合优化问题的离散近似解算法，由于这些问题都是NP难的，因此精确解往往是不可行的;在这种情况下，近似算法是一种可行的选择。除了攻击似乎需要新策略的近似问题外，另一个主要目标是研究传统离散优化问题的设计原理对发生在其他领域的可比较任务的适用性。在任何情况下，严格的性能分析总是有意的。第一个焦点是P-完全永久问题，这是非常重要的统计物理学和组合。粗糙近似（直到指数因子）可以在确定的多项式时间内获得，甚至可能在并行机上更快。这样的解决方案将允许解决并行计算中突出的二分匹配问题。即使匹配问题是对于一个顺序机来说，协调并行机的多个处理器同时有效地处理同一匹配问题是一个很大的挑战。本文还提出了一种新的网络优化方法来解决并行匹配问题。本文的另一个主题是用传统的方法，如局部搜索、比较法、半步优化、甚至有人建议研究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.