Development and analysis of methods of approximation for NP-hard optimization problems

这项研究的目的是开发新的范例来设计和分析一类广泛的NP-Hard优化问题的实用算法。我们将建立在我们之前的基于线性规划的算法的NP-Hard优化问题的研究的基础上，NSERC发现拨款自2003年以来一直在支持这项研究。本研究既具有理论性，又具有应用性。它涉及到新算法的开发和关于解质量的性质的证明。下面，我们概述了提案中的总体方法、具体问题和有待解决的问题。用一个指数大小的LP来模拟一个问题，解决它(可能使用原始-对偶方法)，然后将解转换成一个整数解的方法非常成功(参见Vazirani和Williamson和Shmoys的书)。LP和四舍五入方案都是针对特定问题的。困难在于获得适当的Lp松弛和良好的舍入方案。另一种方法是一次对LP的一个变量进行舍入。使用LP的最优解来确定其值将被固定的变量。固定一个变量的值将产生一个新的LP，迭代过程求解新的LP并设置另一个变量的值。这种迭代舍入的方法在解决网络设计领域的问题方面取得了巨大的成功(参见Liu等人的书)。给定一个整数规划，例如min c x，Ax&gt；=b，定义积分间隙为所有c，A，b的最优积分解的成本与Lp松弛的最优分数解成本之比的上确界。舍入给出一个整数解，Lp松弛给出下界。因此，整数规划的完整性差限制了该方法的逼近比。因此，具有小完整性间隙的程序是非常可取的。这就需要开发特定于问题的切割约束。为了支持长期目标，该研究计划的短期目标是为非对称TSP、D2D信道分配和最小可满足性开发更好的近似算法。我们将处理这些变量存在内在不确定性且不能用简单的整数规划来描述的问题。这项研究将开发出在不确定情况下近似预期成本解决方案的方法。我们还将在本程序中使用和增强基于拉格朗日的技术。这一研究方案将提高我们对启发式算法成功的理论认识，也将对NP-Hard优化问题的算法设计实践产生影响。该研究计划将培养新一代HQP，准备为ML、区块链和量子等新兴技术做出贡献，这些技术依赖于不断改进的优化方法。它将产生具有商业化潜力的知识。

The objective of this research is to develop new paradigms to design and analyze practical algorithms for a broad class of NP-hard optimization problems. We will build on our prior study on linear programming based algorithms for NP-hard optimization problems, supported by NSERC Discovery Grants since 2003. This research is both theoretical and applied in nature. It involves the development of new algorithms and proving properties about the quality of the solution. Below, we outline the general methodology, the specific problems and open questions particular to the proposed program are in the proposal. The approach of modelling a problem by an exponentially sized LP, solving it (possibly using the primal-dual method), and then converting the solution to an integer solution has been immensely successful (see books by Vazirani and Williamson and Shmoys). Both the LP and the rounding scheme are problem-specific. The difficulty is in obtaining a proper LP relaxation, and a good rounding scheme. Another approach is to round the LP one variable at a time. An optimal solution to the LP is used to determine the variable whose value will be fixed. Fixing the value of one variable leads to a new LP, and the iterative process solves the new LP and sets the value of another variable. This method of iterative rounding and has been hugely successful in solving problems in the area of network design (see the book by Lau et al.). Given an integer program say, min c x, A x >= b, define the integrality gap to be the supremum of the ratio of the cost of the optimal integral solution to the cost of the optimal fractional answer to the LP relaxation for all c, A, b. The rounding gives an integral solution, and the LP relaxation gives the lower bound. Therefore, the integrality gap of the integer program bounds the approximation ratio for this approach. Program with small integrality gap is thus highly desirable. This necessitates  the development of problem-specific cut constraints.  In support of the long term objectives the short term objectives of this research program are to develop  better approximation algorithms for asymmetric TSP, D2D channel allocation and minimum satisfiability.  We will work with problems where  there is inherent uncertainty on the  variables and cannot be described  by simple integer programs. This  research will develop methods to approximate the expected cost solutions  under uncertainty. We will use and augment Lagrangian based techniques in this program as well. This research program will improve our  theoretical understanding of the success of heuristics.  The research will also impact the praxis of algorithm design for NP-hard optimization problems. The research program will train a new generation of HQP ready to contribute to emerging technologies such as ML, Blockchain and Quantum, which rely on forever improved methods of optimization. It will generate knowledge with potential for commercialization.