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

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

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.