Approximation algorithms for packing and network problems

打包和网络问题的近似算法

• 批准号: 227829-2009
• 负责人: SolisOba, Roberto
• 金额: $ 1.75万
• 依托单位: University of Western Ontario
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=546839
• 关键词: Approximation; algorithms; packing; network; problems

A large number of practical optimization problems belong to the class NP-hard and, unfortunately, there is strong theoretical evidence suggesting that optimum solutions for NP-hard problems cannot be computed efficiently. Approximation algorithms are fundamental tools for dealing with this class of problems, as these algorithms can efficiently produce solutions that are guaranteed to be at most some factor c away from the optimum. Thus, a natural goal when designing approximation algorithms is to make this factor c as close to 1 as possible. In this research we are mainly interested in studying approximation algorithms for NP-hard optimization problems of two classes: packing and network problems. Networks are one of the most fundamental modeling tools in optimization, with applications to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other area requiring the arrangement of objects in bounded spaces.

大量的实际优化问题属于NP-Hard问题，不幸的是，有强有力的理论证据表明，NP-Hard问题的最优解不能有效地计算出来。近似算法是处理这类问题的基本工具，因为这些算法可以有效地产生保证最多偏离最优解c倍的解。因此，设计近似算法时的一个自然目标是使该因子c尽可能接近于1。在这项研究中，我们主要研究两类NP-Hard优化问题的近似算法：布局问题和网络问题。网络是最优化中最基本的建模工具之一，在许多领域都有应用。布局问题在运输、VLSI设计、调度以及任何其他需要在有限空间中布置对象的领域中都是非常重要的。