|
Abstract:
|
A Steiner system S(t; k; v) is a set which contains v elements (v-set) and a family
of k-subsets (blocks), such that each t-subset appears in exactly one block (v > k >
t > 1; v; k; t 2 N). In the case of a (v; k; t)¡covering, each t-subset appears in at
least one block of a given family. A Steiner system S(t; k; v) exists if and only if
C(v; k; t) =
¡v
t
¢±¡k
t
¢
, where C(v; k; t) is the cardinality of minimal (v; k; t)¡covering.
As the existence of Steiner system S(t; k; v) and the determination of the minimal
(v; k; t)¡covering are still open problems, their solutions are known only in some
special cases.
Besides the review of the previous results related to the problem of the existence
of Steiner systems and the problem of determining the minimal (v; k; t)¡covering,
several new constructions of (v; k; t)¡covering are given in this paper. Since the
number of blocks in (v; k; t)¡covering represents the upper bound on C(v; k; t), a
large number of upper bounds are also obtained by using these constructions. In
many cases, the obtained upper bounds are better than the best known upper bounds
on C(v; k; t).
This dissertation gives a new combinatorial construction of minimal (v; 3; 2)¡
coverings, which represents a generalization of Bose and Skolem constructions of
the Steiner triple systems STS(6n + 3) and STS(6n + 1). In each of the 6 cases
(v = 6n; : : : ; 6n+5), (v; 3; 2)¡covering is obtained by applying certain permutation
p to the initial set of blocks. The obtained construction also represents a new proof
of the statement that the values of C(v; 3; 2) are equal to SchÄonheim lower bound
L(v; 3; 2).
Other constructions of (v; k; t)¡coverings, given in this paper, are heuristic.
First, we give improved implementation of the well known greedy algorithm. Then,
a new greedy algorithm, as well as the theorem which provides a su±cient con-
dition for equality of greedy lex and greedy colex coverings are given. Finally, by
v
using so called LR procedure, three other heuristics are developed and implemented:
Large neighbourhood search, Variable neighborhood descent and General variable
neighborhood search.
Large neighbourhood search is the procedure of alternately destroying and re-
pairing a solution in order to improve the incumbent solution. In the proposed
algorithm, this is the procedure for systematic removing and adding blocks to the
covering, based on LR procedure. By using LR procedure, the blocks which exclu-
sively cover the minimal number of t-subsets are removed from (v; k; t)¡covering,
and then the uncovered t-subsets are covered with as few blocks as possible. The
greedy algorithm is used for the covering of the uncovered t-subsets.
Variable neighborhood search is based on the idea of systematic change of neigh-
borhood within a local search algorithm in order to avoid the convergence to a local
minimum. A variant of the method where changes of neighborhood is performed
in a deterministic way is called Variable neighborhood descent. A variant where
the local search procedure is replaced by the Variable neighborhood descent method
is General variable neighborhood search. The basis of the local search procedure
applied in these two heuristics is also LR procedure.
Regarding quality of the obtained results and the performance of the methods,
Large neighbourhood search, Variable neighborhood descent, and General variable
neighborhood search overcome two heuristics for solving the problem of minimal
(v; k; t)¡covering known from the literature: Simulated annealing and Tabu search.
Unlike the existing heuristics, the proposed heuristics are applicable to arbitrarily
(v; k; t)¡covering. By applying aforementioned heuristics, 23 new best known upper
bounds on C(v; k; t) are established. |