Group Partition, Factorization and the Vector Covering Problem

Abstract

The covering problem . Let S i ( i = 1, 2,…, n ) be given sets containing m i elements respectively and let 1 be their cartesian product. The elements of S ( n ) will be called vectors . The vector (x 1 x 2 ,…, x n ) covers (y 1 y 2 ,…, y n ) if x i =y i for at least n —1 values of i . A subset M of S ( n ) is said to be a covering ( perfect covering ) of S ( n ) if each member of S ( n ) is covered by at least ( exactly ) one member of M . A covering M is said to be linear if the sets S i are groups G i and M is a subgroup of G ( n ) = S ( n ) Denote by σ(n; m 1 m 2 ,…, m n ) the value of min | M | when M runs through all coverings of S (n) and by σ(n; m 1 m 2 ,…, m n ) the value of min | M | when the sets S i are given groups G i and M runs through all linear coverings of G ( n ) .