Name
Abstract | ||
|---|---|---|
Abstract The linear sum assignment problem is a fundamental combinatorial optimisation problem and can be broadly defined as: given an \(n \times m, m \ge n\) benefit matrix \(B = (b_{ij})\), 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 (\(n \ne m\)) 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s10878-015-9979-2 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Heuristic search,Optimization,Linear sum assignment,Protein structure alignment | Weapon target assignment problem,Discrete mathematics,Mathematical optimization,Combinatorics,Heuristic,Heuristic (computer science),Matrix (mathematics),Generalized assignment problem,Greedy algorithm,Assignment problem,Linear bottleneck assignment problem,Mathematics | Journal |
Volume | Issue | ISSN |
33 | 2 | 1573-2886 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Brown | 1 | 1 | 0.69 |
| Yuedong Yang | 2 | 196 | 23.47 |
| Yaoqi Zhou | 3 | 109 | 8.72 |
| Wayne J. Pullan | 4 | 232 | 12.73 |