Advanced search options

You searched for `subject:(combinatorial optmisation)`

. One record found.

▼ Search Limiters

University of Sydney

1.
Sheppard, Nicholas Paul.
Self-Reduction for *Combinatorial* Optimisation
.

Degree: 2001, University of Sydney

URL: http://hdl.handle.net/2123/797

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.

Subjects/Keywords: combinatorial optmisation; self-reduction; confluence; decomposition; graph colouring; steiner problem; bin packing; set covering

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Sheppard, N. P. (2001). Self-Reduction for Combinatorial Optimisation . (Thesis). University of Sydney. Retrieved from http://hdl.handle.net/2123/797

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Sheppard, Nicholas Paul. “Self-Reduction for Combinatorial Optimisation .” 2001. Thesis, University of Sydney. Accessed October 31, 2020. http://hdl.handle.net/2123/797.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Sheppard, Nicholas Paul. “Self-Reduction for Combinatorial Optimisation .” 2001. Web. 31 Oct 2020.

Vancouver:

Sheppard NP. Self-Reduction for Combinatorial Optimisation . [Internet] [Thesis]. University of Sydney; 2001. [cited 2020 Oct 31]. Available from: http://hdl.handle.net/2123/797.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Sheppard NP. Self-Reduction for Combinatorial Optimisation . [Thesis]. University of Sydney; 2001. Available from: http://hdl.handle.net/2123/797

Not specified: Masters Thesis or Doctoral Dissertation