|
Repositories |
|---|
This repository site contains regularly updated information on three combinatorial optimisation problems in graph theory, which are referenced in a number of scientific papers. There problems are (i) The Ramsey Problem for Multipartite Graphs for which lower bounds are listed and motivated in table form, (ii) The Lottery Problem for which lower and upper bounds on respecitvely the resource utilisation numbers and the lottery numbers are listed and motivated in table form, and (iii) The Scheduled Multiple Traversal Postman Problem (SMTPP) for which solutions to 180 bench mark problems are documented.
The Set Multipartite Ramsey Problem may somewhat imprecisely be defined as follows: What is the smallest natural number p such that, if the edges of a complete, balanced multipartite graph (consisiting of p partite sets of a fixed, pre-determined number of vertices per partite set) are arbitrary colouring using the two colours red and blue, one necessarily forces a red pre-specified multipartite subgraph G(red) or a blue pre-specified multipartite subgraph G(blue) (or both) in the colouring? Denote the answer to this problem by the set multipartite Ramsey number, p.
The Size Multipartite Ramsey Problem, on the other hand, may somewhat imprecisely be defined as follows: What is the smallest natural number p' such that, if the edges of a complete, balanced multipartite graph (consisiting of a fixed, pre-determined number of partite sets, each in turn containing p' vertices) are arbitrary colouring using the two colours red and blue, one necessarily forces a red pre-specified multipartite subgraph G(red) or a blue multipartite pre-specified subgraph G(blue) (or both) in the colouring? Denote the answer to this problem by the size multipartite Ramsey number, p'.
More rigorous definitions of the notions of set multipartite Ramsey numbers and size multipartite Ramsey numbers may be found in the following papers respectively:
 |
AP Burger & JH van Vuuren, Multipartite graph theoretic Ramsey numbers. Part I: Set Numbers, submitted, 2001. [Abstract] |
|
AP Burger & JH van Vuuren, Multipartite graph theoretic Ramsey numbers. Part II: Size Numbers, submitted, 2001. [Abstract] |
These problems were originally defined in the following paper for the special diagonal case (i.e. where G(red)=G(blue)):
|
AP Burger, PJP Grobler, E Stipp & JH van Vuuren, Diagonal Ramsey numbers for multipartite graphs, to appear in Utilitas Mathematica. [Abstract] |
(
31 Dec 2001) Tables containing best known lower bounds on these multipartite Ramsey numbers for small graphs may be found
here. Motivations for these bounds may be found in the first two papers listed above.
Suppose a lottery scheme consists of randomly selecting a winning n-set from a universal m-set, while a player participates in the scheme by purchasing a playing set of any number of n-sets from the universal set prior to the draw, and is awarded a prize if k or more numbers in the winning n-set match those of at least one of the player's n-sets in his playing set (k <= n <= m). The player may wish to construct his playing set in such a way that it will necessarily contain at least one n-set which matches at least k numbers in the winning n-set, no matter which winning n-set is chosen from the universal set. Alternatively the player might only be able to purchase a playing set of cardinality l, in which case he may wish to construct his playing set so as to maximise his chances of winning a lottery k-prize. These two situations give rise to the so-called incomplete lottery problem and to the resource utilisation problem, for which rigorous definitions may be found here. These two problems and properties of their solutions are considered in the following papers:
|
AP Burger, WR Gründlingh & JH van Vuuren, The lottery problem, in preparation. [Abstract] |
|
AP Burger, WR Gründlingh & JH van Vuuren, Two combinatorial problems concerning lotteries. Part I: Algorithmic determination of solution sets, in preparation. |
|
AP Burger, WR Gründlingh & JH van Vuuren, Two combinatorial problems concerning lotteries. Part II: Characterising solution set structures, in preparation. |
Repository tables of best known upper bounds on incomplete lottery numbers for small lotteries will be placed here in due
course.
Repository tables of best known lower bounds on resource utilisation numbers for small lotteries will be placed here in due
course.
Repository diagrams and tables containing complete characterisations of solution sets to the above two combinatorial optimisation
problems will be placed here in due course.
The SMTPP may somewhat imprecisely bedefined as follows: Given a weighted graph, to determine an efficient circular traversal of the graph that requires a subset of its edges to be traversed, each a specified (potentially different) number of times. Additionally, consecutive time instances at which the same edge has to be traversed should be spaced through a scheduling time window as evenly as possible, thus introducing a scheduling consideration to the problem.
The SMTPP emerged as a new contribution to the literature on vehicle problems as a result of an interesting service vehicle scheduling problem experienced by SPOORNET (the South African National Railways Authority and Service Provider). This problem is described and solved in the following paper:
|
GW Groves, J le Roux & JH van Vuuren, Scheduling evenly spaced vehicle routes in networks, submitted 2002. [Abstract] |
The problem is formulated in a more general setting and the efficiency of a proposed heuristic solution procedure for the SMTPP is tested on 180 documented benchmark instances of the problem in the following paper:
|
GW Groves, J le Roux & JH van Vuuren, On a routing & scheduling problem concerning multiple edge traversals in graphs, submitted 2002. [Abstract] |
(
23 Dec 2002) A repository of the 180 benchmark problems may be found here.
The 2D Strip packing problem belongs to a class of packing problems defined as: Given an open ended bin (referred to as a strip) of fixed width and infinite height, a list of items with dimensions (w,h) is required to be packed without overlapping such that the total packing height is minimised.
Packing problems have been of interest to many researchers for decades because of their various applications to business and industry.
A number of algorithms from literature and some newly proposed heuristics for the 2D strip packing problem were tested on 542 documented benchmark instances of the problem in the following paper:
|
N Ntene, JH van Vuuren, A survey and comparison of level heuristics for the 2D oriented strip packing problem , submitted 2006. [Abstract] |
( 13 Feb 2006) A repository of the 542 benchmark problems may be found here.