Please use this identifier to cite or link to this item:
http://hdl.handle.net/2123/797
|
| Title: | Self-Reduction for Combinatorial Optimisation |
| Authors: | Sheppard, Nicholas Paul |
| Keywords: | combinatorial optmisation;self-reduction;confluence;decomposition;graph colouring;steiner problem;bin packing;set covering |
| Issue Date: | 2006 |
| Publisher: | University of Sydney. Computer Science |
| Abstract: | This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems. |
| URI: | http://hdl.handle.net/2123/797 |
| Appears in Collections: | Sydney Digital Theses
|
Items in Sydney eScholarship Repository are protected by copyright, with all rights reserved, unless otherwise indicated.