Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
基本信息
- 批准号:RGPIN-2014-06302
- 负责人:
- 金额:$ 1.46万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2014
- 资助国家:加拿大
- 起止时间:2014-01-01 至 2015-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
It is generally believed that efficient algorithms do not exist for finding an optimal solution to NP-hard opti- mization problems. A natural way to deal with the inability to find exact solutions efficiently is to trade the quality of solution for the computation time. Approximation algorithms do precisely that. Approximation algorithms not only provide an approximate solution in polynomial time, they also provide a certificate of optimality for the solution. One can always refine and tune an approximation algorithm to specific class of instances arising in practice, thereby improving the performance ratio. Primary goal of this research is to further the theory and praxis of the design of approximation algorithms. We will design approximation algorithms for problems arising in the bioinformatics, facility location, schedul- ing, and machine learning domains. Our approach for designing approximation algorithms has theoretical underpinnings in combinatorial algorithms, linear and semi-definite programming. Linear programming based approaches have enjoyed a great deal of success in the recent past. The basic framework entails de- scribing the optimization problem as an integer linear program or a non-linear program over integer variables. A suitable linear programming relaxation or a semi-definite programming relaxation is constructed. The re- laxation is solved using efficient algorithms. A fractional solution thus obtained is converted to an integral solution using some scheme. Care is taken to ensure that the process of converting the fractional solution to an integral solution does not increase the cost of the solution too much. Another approach is to simultane- ously construct an integral primal solution and candidate dual solution (possibly fractional) iteratively using the primal-dual schema. Primal-dual schema has the advantage that one can work with an exponential sized formulation without having to resort to a separation oracle. Approaches based on the primal-dual schema have been very successful for certain types of optimization problems. Integrality gap of an integer program- ming formulation is the gap in the cost of the optimal fractional and the cost of the optimal integral solution. Approximation algorithms based on linear or semi-definite programming have performance ratio no better than the integrality gap of the relaxation. Therefore integer programs with small integrality gap are critical to the success of such approximation algorithms. The immediate program is i) to develop relaxations with bounded integrality gap for the optimization problems of interest or show none exists, ii) to develop combi- natorial algorithms for solving the relaxations where possible, and iii) to develop provably good strategies for converting the fractional solutions to the relaxations to integral solution. There has been considerable research activity on the hardness of approximations in the last few years and several deep results on the hard- ness of approximations have been obtained. The focus of this research is on the design of approximation algorithms and we will draw on the results on hardness of approximations to guide the program. On the theoretical front we will push the frontier in approximation algorithms design. Research conducted as part of this project will have prospect for commercialization and will be of immediate interest to the industry. Knowledge generated will be protected using patents (where applicable) and disseminated in high quality journals and conferences. The program will produce highly skilled manpower; skilled in the use of discrete optimization theory and tools.
一般认为,对于NP-hard优化问题,不存在寻找最优解的有效算法。解决无法有效地找到精确解的一种自然方法是用解的质量来换取计算时间。近似算法就是这样做的。近似算法不仅在多项式时间内提供近似解,而且还提供了解的最优性证明。人们总是可以根据实践中出现的特定类别的实例来改进和调整近似算法,从而提高性能比率。本研究的主要目的是进一步推动近似算法设计的理论和实践。我们将为生物信息学、设施定位、调度和机器学习领域中出现的问题设计近似算法。我们设计近似算法的方法有组合算法、线性和半确定规划的理论基础。基于线性规划的方法在最近取得了很大的成功。其基本框架要求将优化问题描述为整数线性规划或整数变量上的非线性规划。构造了合适的线性规划松弛或半确定规划松弛。利用高效的算法解决了松弛问题。用某种格式将得到的分数解转化为积分解。要注意确保将分数解转换为积分解的过程不会过多地增加解的成本。另一种方法是使用原始-对偶模式同时迭代构造一个积分原始解和候选对偶解(可能是分数)。原始对偶模式的优点是可以使用指数大小的公式,而不必求助于分离oracle。基于原始对偶模式的方法对于某些类型的优化问题已经非常成功。整数规划公式的完整性缺口是最优分数的代价与最优积分解的代价之间的缺口。基于线性或半确定规划的近似算法的性能比不优于松弛的完整性间隙。因此,具有小完整性间隙的整数规划是这种近似算法成功的关键。直接计划是i)为感兴趣的优化问题开发具有有界积分间隙的松弛或显示不存在,ii)开发组合算法在可能的情况下解决松弛,iii)开发可证明的良好策略将分数解转换为松弛到积分解。近年来,人们对近似的硬度进行了大量的研究,并取得了一些较为深刻的结果。本研究的重点是近似算法的设计,我们将借鉴近似硬度的结果来指导程序。在理论方面,我们将推动近似算法设计的前沿。作为该项目的一部分进行的研究将具有商业化的前景,并将直接引起行业的兴趣。所产生的知识将使用专利(如适用)加以保护,并在高质量的期刊和会议上传播。该计划将培养高技能人才;熟练运用离散优化理论和工具。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Gaur, Daya其他文献
Gaur, Daya的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Gaur, Daya', 18)}}的其他基金
Development and analysis of methods of approximation for NP-hard optimization problems
NP 困难优化问题的近似方法的开发和分析
- 批准号:
RGPIN-2021-03828 - 财政年份:2022
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Development and analysis of methods of approximation for NP-hard optimization problems
NP 困难优化问题的近似方法的开发和分析
- 批准号:
RGPIN-2021-03828 - 财政年份:2021
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2018
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2016
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2015
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Linear programming based approximation algorithms for optimization problems
基于线性规划的优化问题近似算法
- 批准号:
262126-2009 - 财政年份:2010
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Linear programming based approximation algorithms for optimization problems
基于线性规划的优化问题近似算法
- 批准号:
262126-2009 - 财政年份:2009
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for optimization problems
优化问题的近似算法
- 批准号:
262126-2008 - 财政年份:2008
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for combinatorial optimization problems
组合优化问题的近似算法
- 批准号:
262126-2003 - 财政年份:2007
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2022
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2021
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2020
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-Hard Problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2019-04197 - 财政年份:2019
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2018
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2018
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for NP-hard Optimization Problems
NP 难优化问题的近似算法
- 批准号:
RGPIN-2014-06302 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual
Approximation algorithms for NP-hard graph connectivity problems
NP 难图连通性问题的近似算法
- 批准号:
509110-2017 - 财政年份:2017
- 资助金额:
$ 1.46万 - 项目类别:
University Undergraduate Student Research Awards
Approximation algorithms for NP-hard problems
NP 困难问题的近似算法
- 批准号:
RGPIN-2014-04351 - 财政年份:2016
- 资助金额:
$ 1.46万 - 项目类别:
Discovery Grants Program - Individual