{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/25001"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/25001","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"EFFICIENT DATA ASSOCIATION ALGORITHMS FOR MULTI-TARGET TRACKING","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Li, Jingqun"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Electrical and Computer Engineering","school":null,"contributors":[],"advisors":["Kirubarajan, Thia"],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-11-18T19:34:00Z","subjects":["Binary programming","Optimization","Multi-target tracking","assignment problem"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/15548"],"render_values":[{"text":"https://doi.org/10.71548/15548","href":"https://doi.org/10.71548/15548","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/25001","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/25001","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F25001","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Kirubarajan, Thia"]},{"key":"dc:contributor.department","label":"Department","values":["Electrical and Computer Engineering"]},{"key":"dc:creator","label":"Author","values":["Li, Jingqun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-10-07T14:35:27Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-10-07T14:35:27Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Binary programming","Optimization","Multi-target tracking","assignment problem"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/25001","https://doi.org/10.71548/15548"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Efficient multi-dimensional assignment algorithms and their application in multi-frame tracking"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Doctor of Philosophy (PhD)"]},{"key":"dc:title","label":"Title","values":["EFFICIENT DATA ASSOCIATION ALGORITHMS FOR MULTI-TARGET TRACKING"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Kirubarajan, Thia"],"dc:contributor.department":["Electrical and Computer Engineering"],"dc:creator":["Li, Jingqun"],"dc:date.accessioned":["2019-10-07T14:35:27Z"],"dc:date.available":["2019-10-07T14:35:27Z"],"dc:date.issued":["2019"],"dc:description":["Efficient multi-dimensional assignment algorithms and their application in multi-frame tracking"],"dc:description.abstract":["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."],"dc:description.degree":["Doctor of Philosophy (PhD)"],"dc:identifier.uri":["http://hdl.handle.net/11375/25001","https://doi.org/10.71548/15548"],"dc:language.iso":["en"],"dc:subject":["Binary programming","Optimization","Multi-target tracking","assignment problem"],"dc:title":["EFFICIENT DATA ASSOCIATION ALGORITHMS FOR MULTI-TARGET TRACKING"],"dc:type":["Thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:34:00Z"}