Please use this identifier to cite or link to this item:
|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: ||2001|
|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.|
|Rights and Permissions: ||Copyright Sheppard, Nicholas Paul;http://www.library.usyd.edu.au/copyright.html|
|Appears in Collections:||Sydney Digital Theses (Open Access)|
This work is protected by Copyright. All rights reserved. Access to this work is provided for the purposes of personal research and study. Except where permitted under the Copyright Act 1968, this work must not be copied or communicated to others without the express permission of the copyright owner. Use the persistent URI in this record to enable others to access this work.
Items in Sydney eScholarship Repository are protected by copyright, with all rights reserved, unless otherwise indicated.