No description available.

M.Sc. (Computer Science) / The STSP (symmetric travelling salesman problem) involves finding the cheapest tour through a number of cities. It is a difficult problem and until recently algorithms for the TSP could not find the optimal tour in a reasonable time if the number of cities exceeded 100. In 1987 Padberg and Rinaldi published their computational experience with a new branch-and-cut algorithm. They were able to solve problems with up to 2392 cities on a CDC CYBER 205 supercomputer. Padberg and Rinaldi used a standard LP (linear programming) solver in their implementation of the branch-and-cut algorithm. The algorithm first solves the continuous 2-matching problem (RMP2) using the LP solver. It then repeatedly identifies constraints of the TSP which are not satisfied by the current RMP2-solution and solve RMP2 with the identified TSP-constraints as side constraints. However, RMP2 is a linear programming problem with a very special structure which we exploited in an implementation of the primal simplex algorithm for RMP2. Our computational experience with this implementation indicates that it is almost 400 times faster than a commercial LP solver on problems with 200 cities. We developed an implementation of the dual simplex algorithm which exploits the special structure of both RMP2 and the side constraints identified in the branch-and-cut algorithm. An existing set of side constraints for solving a 48-eity problem was used to test our implementation of the dual simplex algorithm. We implemented the procedure described by Padberg & Rinaldi to identify subtour elimination side constraints (one type of side constraint) for the 48-eity problem. Our implementation of the identification procedure was then used in conjunction with our implementation of the dual simplex algorithm. The maximum flow problem has to be solved in the algorithm for identification of subtour elimination constraints. We implemented the Sleator-Tarjan algorithm for this purpose.

M.Sc. (Computer Science) / The Travelling Salesman Problem (TSP) comprises the following: A salesman is required, by definition of his job description, to visit a set of cities. He leaves from a base city, visits each of the other cities exactly once and then returns to his base city. In travelling between city pairs, he incurs certain costs. It is a travelling salesman's constant endeavour, therefore, to find the cheapest route. A combinatorial optimisation problem involves the selection of the best alternative from a finite set of alternatives. The TSP is one of the best known and most studied combinatorial optimisation problems. At present, the branch-and-cut algorithm of Padberg and Rinaldi is the most successful algorithm for solving large-scale instances of the TSP. Padberg and Rinaldi used a general LP solver to solve the subproblem P(L, F0 , F1 ), where L is a set of side constraints, F0 is the set of variables fixed at 0 and F1 is the set of variables fixed at 1. As noted by Smith and Leenen, however, this subproblem has a special structure that was exploited by them to solve the subproblem more efficiently. In this dissertation, we would like to present improvements on Leenen's contribution. For this purpose, we compared our results with those of a commercial LP solver. It was found that our program on average executed in half the time of that of the commercial LP solver. The problem P(L, F0 , F1;) has to be solved many times in the branch-and-cut algorithm before a solution to the TSP is obtained. For large-scale instances of the TSP, a substantial portion of the execution time of the entire branch-and-cut algorithm is spent in the linearprogram optimiser. The branch-and-cut algorithm could,• therefore, be potentially more efficient if the special structure were utilised. We constructed a full implementation of the branch-and-cut algorithm, utilising the special structure. We did not, however, implement all the refinements discussed by Padberg and Rinaldi. Padberg and Rinaldi used four classes of TSP constraints: subtour elimination, 2-matching, comb and clique-tree inequalities. Owing to time constraints and the complexity of identifying the other classes of constraints, we decided to implement subtour elimination constraints only. We subsequently compared our results with those of Padberg and Rinaldi, and realised that we totally underestimated the importance of using more classes of constraints. Our search trees had become extremely huge. We realised, therefore, that more classes of constraints were essential for solving large instances of the TSP. Even though numerical errors still posed a problem, they might disappear if the size of the search tree were reduced to that obtained by Padberg and Rinaldi.

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Computer Science / Master / Master of Philosophy

published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

This thesis describes the implementation of an ELINT algorithm for the detection and classification of Low Probability of Intercept (LPI) signals. The algorithm was coded in the C programming language and executed on a Field Programmable Gate Array based reconfigurable computer; the SRC-6 manufactured by SRC Computers, Inc. Specifically, this thesis focuses on the preprocessing stage of an LPI signal processing algorithm. This stage receives a detected signal that has been run through a Quadrature Mirror Filter Bank and outputs the preprocessed signal for classification by a neural network. A major value of this study comes from comparing the performance of the reconfigurable computer to that of supercomputers and embedded systems that are currently used to solve the signal processing needs of the United States Navy. / US Navy (USN) author.

After that, strip sum and orthogonal Haar transform are proposed. The sum of pixels in a rectangle can be computed by one addition using the strip sum. Then this thesis proposes to use the orthogonal Haar transform (OHT) for pattern matching. Applied for pattern matching, the fast OHT algorithm using strip sum requires O(log u) additions per pixel to project input data of size N1 x N2 onto u 2-D OHT bases. Experimental results show the efficiency of pattern matching using OHT. / Firstly, this thesis proposes a fast algorithm for Walsh Hadamard Transform (WHT) on sliding windows which can be used to implement pattern matching efficiently. / Support vector machine (SVM) is a widely used classification approach. Direct computation of SVM is not desirable in applications requiring computationally efficient classification. To relieve the burden of high computational time required for computing SVM, this thesis proposes a transform domain SVM (TDSVM) using pruning that computes SVM much faster. Experimental results show the efficiency in applying the proposed method for human detection. / Then this thesis analyzes and compares state-of-the-art algorithms for full search equivalent pattern matching. Inspired by the analysis, this thesis develops a new family of transforms called the Kronecker-Hadamard Transform (KHT) of which the GCK family is a subset and WHT is a member. Thus, KHT provides more choices of transforms for representing images. Then this thesis proposes a new fast algorithm that is more efficient than the GCK algorithm. All KHTs can be computed efficiently using the fast KHT algorithm. Based on the KHT, this thesis then proposes the segmented KHT (SegKHT). By segmenting input data into Ls parts, the SegKHT requires 1/Ls the computation required by the KHT algorithm in computing basis vectors. Experimental results show that the proposed algorithm can significantly accelerate the pattern matching process and outperforms state-of-the-art methods. / This thesis aims at improving the computational efficiency in pattern matching. / Ouyang, Wanli. / Adviser: Wai Kuen Cham. / Source: Dissertation Abstracts International, Volume: 73-04, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 143-147). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.