Skip to main content

Algorithms and theoretical topics on selected combinatorial optimization problems

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2010-12-03
Authors/Contributors
Author: Kaveh, Arman
Abstract
We study the Quadratic Assignment Problem (QAP), Three Dimensional Assignment Problem (3AP) and Quadratic Three Dimensional Assignment Problem (Q3AP), which combines aspects of both QAP and 3AP. The three problems are known to be NP-hard. We propose new algorithms for obtaining near optimal solutions of QAP and 3AP and present computational results. Our algorithms obtain improved solutions in some benchmark instances of QAP and 3AP. We also discuss theoretical results on 3AP and Q3AP such as polynomially solvable special cases and approximation algorithms. A special case of 3AP is the constant 3AP where every feasible solution has the same cost. Necessary and sufficient conditions are presented for an instance of 3AP to have a constant solution and the result is extended to Multidimensional Assignment Problems (MAP).
Document
Identifier
etd6350
Copyright statement
Copyright is held by the author.
Permissions
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact summit-permissions@sfu.ca.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Punnen, Abraham
Member of collection
Download file Size
etd6350_AKaveh.pdf 851.92 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0