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

点击翻译按钮获取中文摘要

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.