二次分配问题的推广模型及近似算法研究

This project will focus on the following several problems. (1) Most of the existing literatures on the quadratic assignment problem only consider the input matrix is a nonpositive symmetric square. This project will consider its generalized model and its approximation algorithm with lower bound; (2) Based on the essential relations between the quadratic assignment problem and graph matching problem, this project will try to combine them organically, make the results can draw from each other. Based on our results on alternative iteration algorithm and two-way relaxation barrier model for graph matching, we will apply it to the quadratic assignment problem.

本项目将以二次分配问题及其推广模型为研究对象，以近似算法的设计为研究主线，以二次分配问题和图匹配问题的有机结合为特色，聚焦于如下几个问题的研究： . （1）针对现有大部分二次分配问题的仅关注同阶非负对称方阵的情况，本课题将重点考虑一对输入矩阵是一般的同阶方阵和一对输入矩阵是不同阶对称方阵两种情况，并在此基础上考虑有多对输入矩阵的广义二次分配问题及下界近似算法；. （2）基于二次分配问题和图匹配问题的本质联系，且二者的研究相对独立的现状，本课题试图将二者有机结合，使得研究结果能互相借鉴。特别地，基于本人关于“求解图匹配问题的交替迭代算法”和“双向松弛障碍模型”的前期研究成果，尝试将该算法和该障碍模型思路推广并应用于二次分配问题。

本项目以二次分配问题及其推广模型为研究对象，以近似算法的设计为研究主线，以二次分配问题和图匹配问题的有机结合为特色，聚焦于如下几个问题的研究：. （1）针对现有大部分二次分配问题的仅关注同阶非负对称方阵的情况，本课题重点考虑一对输入矩阵是一般的同阶方阵和一对输入矩阵是不同阶对称方阵两种情况，并在此基础上，考虑有多对输入矩阵的广义二次分配问题及下界近似算法；. （2）基于二次分配问题和图匹配问题的本质联系，且二者的研究相对独立的现状，本课题将二者有机结合，使得研究结果能互相借鉴。特别地，基于本人关于“求解图匹配问题的交替迭代算法”和“双向松弛障碍模型”的前期研究成果，将该算法和该障碍模型思路推广并应用于二次分配问题。. 针对（1），已完成题为“The Generalized Quadratic Programming Problem on Orthogonal matrices and its applications to Graph Matching Problem”的文章手稿工作，指出正交阵上的齐次广义QAP问题，可通过秩1松弛技术和Lagrange对偶技术，等价地转化为线性半定规划问题；针对问题（2）已完成题为“交替迭代算法求解二次分配问题”的文章手稿工作，指出在结合其他松弛模型的情况下，用交替迭代算法，能得到精度更高的近似解。