Efficient multi-dimensional assignment algorithms and their application in multi-frame tracking / In this work, we propose a novel convex dual approach to the multidimensional dimensional
assignment problem, which is an NP-hard binary programming problem.
It is shown that the proposed dual approach is equivalent to the Lagrangian relaxation
method in terms of the best value attainable by the two approaches. However,
the pure dual representation is not only more elegant, but also makes the theoretical
analysis of the algorithm more tractable. In fact, we obtain a su cient and necessary
condition for the duality gap to be zero, or equivalently, for the Lagrangian relaxation
approach to nd the optimal solution to the assignment problem with a guarantee.
Also, we establish a mild and easy-to-check condition, under which the dual problem
is equivalent to the original one. In general cases, the optimal value of the dual
problem can provide a satisfactory lower bound on the optimal value of the original
assignment problem.
We then extend the purely dual formulation to handle the more general multidimensional
assignment problem. The convex dual representation is derived and its
relationship to the Lagrangian relaxation method is investigated once again. Also,
we discuss the condition under which the duality gap is zero. It is also pointed out
that the process of Lagrangian relaxation is essentially equivalent to one of relaxing
the binary constraint condition, thus necessitating the auction search operation to
recover the binary constraint. Furthermore, a numerical algorithm based on the dual
formulation along with a local search strategy is presented.
Finally, the newly proposed algorithm is shown to outperform the Lagrangian
relaxation method in a number of multi-target tracking simulations. / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/25001 |
| Date | January 2019 |
| Creators | Li, Jingqun |
| Contributors | Kirubarajan, Thia, Electrical and Computer Engineering |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0023 seconds