A heuristic for the time constrained asymmetric linear sum assignment problem

作者：Brown Peter; Yang Yuedong; Zhou Yaoqi; Pullan Wayne^*

来源：Journal of Combinatorial Optimization, 2017, 33(2): 551-566.

DOI：10.1007/s10878-015-9979-2

• Heuristic search
• Optimization
• Linear sum assignment
• Protein structure alignment

The linear sum assignment problem is a fundamental combinatorial optimisation problem and can be broadly defined as: given an benefit matrix , matching each row to a different column so that the sum of entries at the row-column intersections is maximised. This paper describes the application of a new fast heuristic algorithm, Asymmetric Greedy Search, to the asymmetric version () of the linear sum assignment problem. Extensive computational experiments, using a range of model graphs demonstrate the effectiveness of the algorithm. The heuristic was also incorporated within an algorithm for the non-sequential protein structure matching problem where non-sequential alignment between two proteins, normally of different numbers of amino acids, needs to be maximised.

• 出版日期2017-2