2017/03/27 by José F. S. Bravo-Ferreira, Yuehaw Khoo, Ferreira, Jose F. S. Bravo +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #FOS: Mathematics #Machine Learning and Algorithms #Nuclear Receptors and Signaling #Optimization and Control (math.OC) #Peroxisome Proliferator-Activated Receptors #RNA Interference and Gene Delivery
paper · pdf · doi:10.48550/arxiv.1703.09339
openalex publication_date 2017/03/27 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
The matching problem between two adjacency matrices can be formulated as the\nNP-hard quadratic assignment problem (QAP). Previous work on semidefinite\nprogramming (SDP) relaxations to the QAP have produced solutions that are often\ntight in practice, but such SDPs typically scale badly, involving matrix\nvariables of dimension n2 where n is the number of nodes. To achieve a speed\nup, we propose a further relaxation of the SDP involving a number of positive\nsemidefinite matrices of dimension \O(n) no greater than the number\nof edges in one of the graphs. The relaxation can be further strengthened by\nconsidering cliques in the graph, instead of edges. The dual problem of this\nnovel relaxation has a natural three-block structure that can be solved via a\nconvergent Augmented Direction Method of Multipliers (ADMM) in a distributed\nmanner, where the most expensive step per iteration is computing the\neigendecomposition of matrices of dimension \O(n). The new SDP\nrelaxation produces strong bounds on quadratic assignment problems where one of\nthe graphs is sparse with reduced computational complexity and running times,\nand can be used in the context of nuclear magnetic resonance spectroscopy (NMR)\nto tackle the assignment problem.\n