Approximation Algorithms for Problems of Various Complexities

各种复杂问题的近似算法

• 批准号: 0209099
• 负责人: Martin Furer
• 金额: $ 23.67万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-05-15 至 2006-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0209099&HistoricalAwards=false
• 关键词: Approximation; Algorithms; Problems; Various; Complexities

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.

本研究的目的是设计和分析离散算法逼近组合优化问题的解决方案。因为这些问题中的许多都是np困难的，一个精确的解决方案往往是不可行的；在这种情况下，近似算法是一个可行的选择。除了解决似乎需要新策略的近似问题外，另一个主要目标是研究为传统离散优化问题成功开发的设计原则在其他领域发生的类似任务中的适用性。在任何情况下，都需要进行严格的性能分析。一个。第一个重点是在统计物理和组合学中非常重要的# p -完全永久问题。粗略的近似（直到指数因子）可以在确定性多项式时间内获得，甚至可能在并行机器上更快。这样的解决方案将允许解决并行计算中突出的二部匹配问题。尽管匹配问题对于顺序机来说很容易，但协调并行机的许多处理器同时工作是非常具有挑战性的。在相同的匹配上。并提出了一种新型的传统网络来解决并行匹配问题。噢方法。本提案的另一个主题是用传统方法如局部搜索、比较法、半隐式等逼近NP-hard优化问题。非优化，或者这些的组合。甚至有人建议研究P中一些问题的近似，因为这可能在并行计算中有有趣的应用。