Old and new designs via difference multisets and strong difference families

Let X =((x_1,1,x_1,2,…,x_1,k),(x_2,1,x_2,2,…,x_2,k),…,(x_t,1,x_t,2,…,x_t,k)) be a family of t multisets of size k defined on an additive group G. We say that X is a t-(G,k,μ) strong difference family (SDF) if the list of differences (x_h,i-x_h,j∣h=1,…,t;i≠ j) covers all of G exactly μ times. If a SDF consists of a single multiset X, we simply say that X is a (G,k,μ) difference multiset. After giving some constructions for SDF's, we show that they allow us to obtain a very useful method for constructing regular group divisible designs and regular (or 1-rotational) balanced incomplete block designs. In particular cases this construction method has been implicitly used by many authors, but strangely, a systematic treatment seems to be lacking. Among the main consequences of our research, we find new series of regular BIBD's and new series of 1-rotational (in many cases resovable) BIBD's.     

Constructing cyclic PBIBD(2)s through an optimization approach: Thirty‐two new cyclic designs

We formulate the construction of cyclic partially balanced incomplete block designs with two associate classes (PBIBD(2)s) as a combinatorial optimization problem. We propose an algorithm based on tabu search to tackle the problem. Our algorithm constructed 32 new cyclic PBIBD(2)s. © 2004 Wiley Periodicals, Inc.     

Recursive constructions for difference matrices and relative difference families

We present a new recursive construction for difference matrices whose application allows us to improve some results by D. Jungnickel. For instance, we prove that for any Abelian p-group G of type (n₁, n₂, …, n_t) there exists a (G, p^e, 1) difference matrix with e = Also, we prove that for any group G there exists a (G, p, 1) difference matrix where p is the smallest prime dividing |G|. Difference matrices are then used for constructing, recursively, relative difference families. We revisit some constructions by M. J. Colbourn, C. J. Colbourn, D. Jungnickel, K. T. Phelps, and R. M. Wilson. Combining them we get, in particular, the existence of a multiplier (G, k, λ)-DF for any Abelian group G of nonsquare-free order, whenever there exists a (p, k, λ)-DF for each prime p dividing |G|. Then we focus our attention on a recent construction by M. Jimbo. We improve this construction and prove, as a corollary, the existence of a (G, k, λ)-DF for any group G under the same conditions as above. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 165–182, 1998     

Self-Converse Directed BIBDs with Block Size Four

A directed balanced incomplete block design (or D B(k,;v)) (X,) is called self-converse if there is an isomorphic mapping f from (X,) to (X,^–1), where ^–1={B ^–1:B} and B ^–1=(x _k ,x _{k –1},,x ₂,x ₁) for B=(x ₁,x ₂,,x _{k –1},x _k ). In this paper, we give the existence spectrum for self-converse D B(4,1;v). AMS Classification:05BResearch supported in part by NSFC Grant 10071002 and SRFDP under No. 20010004001     

On the Existence of Simple BIBDs with Number of Elements a Prime Power

We show that, when the number of elements is a prime power q, in many situations the necessary conditions

相似文献   

Some (17q, 17, 2) and (25q, 25, 3) BIBD Constructions

We give the explicit construction of a regular (17q, 17, 2)-BIBD for any prime power q 17 (mod 32) such that 2 is not a 4th power in GF(q) and the explicit construction of a regular (25q, 25, 3)-BIBD for any prime power q 25 (mod 48) such that and +3 are non-squares in GF(q).     

Existence of (q,k, 1) difference families with q a prime power and k = 4, 5

The existence of a (q, k, 1) difference family in GF(q) has been completely solved for k = 3. For k = 4, 5 partial results have been given by Bose, Wilson, and Buratti. In this article, we continue the investigation and show that the necessary condition for the existence of a (q, k, 1) difference family in GF(q), i.e., q ≡ 1 (mod k(k − 1)) is also sufficient for k = 4, 5. For general k, Wilson's bound shows that a (q, k, 1) difference family in GF(q) exists whenever q ≡ 1 (mod k(k − 1)) and q > [k(k − 1)/2]^k(k−1). An improved bound on q is also presented. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 21–30, 1999     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.     

New coverings of t-sets with (t + 1)-sets

The minimum number of k-subsets out of a v-set such that each t-set is contained in at least one k-set is denoted by C(v, k, t). In this article, a computer search for finding good such covering designs, leading to new upper bounds on C(v, k, t), is considered. The search is facilitated by predetermining automorphisms of desired covering designs. A stochastic heuristic search (embedded in the general framework of tabu search) is then used to find appropriate sets of orbits. A table of upper bounds on C(v, t + 1, t) for v 28 and t 8 is given, and the new covering designs are listed. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 217–226, 1999     

Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search

Collections of cans containing nuclear fuel have to be grouped in batches that are as homogeneous as possible with respect to several criteria. This highly combinatorial problem, which can be described as grouping or clustering, is tackled using simulated annealing and tabu search. Both approaches are submitted to extensive experimentation on a real data set and several artificial ones. Two variants of the basic approaches called Locally optimized simulated annealing and Tabu search with variable offset are also tested. Sensitivity to parameter choice and to problem size are investigated. All four algorithms outperform a local search heuristic previously proposed in the literature; on the class of instances dealt with, a remarkably stable ranking of the four algorithms emerges.     

Solving isomorphism problems about 2‐designs from disjoint difference families

Recently, two new constructions of disjoint difference families in Galois rings were presented by Davis, Huczynska, and Mullen and Momihara. Both were motivated by a well‐known construction of difference families from cyclotomy in finite fields by Wilson. It is obvious that the difference families in the Galois ring and the difference families in the finite field are not equivalent. A related question, which is in general harder to answer, is whether the associated designs are isomorphic or not. In our case, this problem was raised by Davis, Huczynska, and Mullen. In this paper, we show that, in most cases, the 2‐ designs arising from the difference families in Galois rings and those arising from the difference families in finite fields are nonisomorphic by comparing their block intersection numbers.     

Partial geometric difference sets and partial geometric difference families

The concept of a partial geometric difference set (or $1\frac{1}{2}$-difference set) was introduced by Olmez in 2014. Recently, Nowak, Olmez and Song introduced the notion of a partial geometric difference family, which generalizes both the classical difference family and the partial geometric difference set. It was shown that partial geometric difference sets and partial difference families give rise to partial geometric designs. In this paper, a number of new infinite families of partial geometric difference sets and partial geometric difference families are constructed. From these partial geometric difference sets and difference families, we generate a list of infinite families of partial geometric designs.     

Realizations for direct constructions of resolvable Steiner 2‐designs with block size 5

We consider direct constructions due to R. J. R. Abel and M. Greig, and to M. Buratti, for ({ν},5,1) balanced incomplete block designs. These designs are defined using the prime fields F_p for certain primes p, are 1‐rotational over G ⊕ F_p where G is a group of order 4, and are also resolvable under certain conditions. We introduce specifications to the constructions and, by means of character sum arguments, show that the constructions yield resolvable designs whenever p is sufficiently large. © 2000 John Wiley & Sons, Inc. J Combin Designs 8:207–217, 2000     

Existence of (q, 7, 1) difference families with q a prime power

The existence of a (q,k, 1) difference family in GF(q) has been completely solved for k = 3,4,5,6. For k = 7 only partial results have been given. In this article, we continue the investigation and use Weil's theorem on character sums to show that the necessary condition for the existence of a (q,7,1) difference family in GF(q), i.e. q ≡ 1; (mod 42) is also sufficient except for q = 43 and possibly except for q = 127, q = 211, q = 31⁶ and primes q∈ [261239791, 1.236597 × 10¹³] such that in GF(q). © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 126–138, 2002; DOI 10.1002/jcd.998     

A New Class of Optimal 3-splitting Authentication Codes

The necessary condition for the existence of a (ν, 3× 3,1)-splitting BIBD is ν ≡ 1 (mod 54). In this paper, we show that the necessary condition is also sufficient with one possible exception of ν = 55. As its application, we obtain a new infinite class of optimal 3-splitting authentication codes. AMS Classification: 05B05, 94A62 An erratum to this article is available at .     

New partial geometric difference sets and partial geometric difference families

Using Galois rings and Galois fields, we construct several infinite classes of partial geometric difference sets, and partial geometric difference families, with new parameters. Furthermore, these partial geometric difference sets (and partial geometric difference families) correspond to new infinite families of directed strongly regular graphs. We also discuss some of the links between partially balanced designs, 2-adesigns (which were recently coined by Cunsheng Ding in “Codes from Difference Sets” (2015)), and partial geometric designs, and make an investigation into when a 2-adesign is a partial geometric design.     

Perfect difference families,perfect difference matrices,and related combinatorial structures

The existence problems of perfect difference families with block size k, k=4,5, and additive sequences of permutations of length n, n=3,4, are two outstanding open problems in combinatorial design theory for more than 30 years. In this article, we mainly investigate perfect difference families with block size k=4 and additive sequences of permutations of length n=3. The necessary condition for the existence of a perfect difference family with block size 4 and order v, or briefly (v, 4,1)‐PDF, is v≡1(mod12), and that of an additive sequence of permutations of length 3 and order m, or briefly ASP (3, m), is m≡1(mod2). So far, (12t+1,4,1)‐PDFs with t<50 are known only for t=1,4−36,41,46 with two definiteexceptions of t=2,3, and ASP (3, m)'s with odd 3<m<200 are known only for m=5,7,13−29,35,45,49,65,75,85,91,95,105,115,119,121,125,133,135,145,147,161,169,175,189,195 with two definite exceptions of m=9,11. In this article, we show that a (12t+1,4,1)‐PDF exists for any t⩽1,000 except for t=2,3, and an ASP (3, m) exists for any odd 3<m<200 except for m=9,11 and possibly for m=59. The main idea of this article is to use perfect difference families and additive sequences of permutations with “holes”. We first introduce the concepts of an incomplete perfect difference matrix with a regular hole and a perfect difference packing with a regular difference leave, respectively. We show that an additive sequence of permutations is in fact equivalent to a perfect difference matrix, then describe an important recursive construction for perfect difference matrices via perfect difference packings with a regular difference leave. Plenty of perfect difference packings with a desirable difference leave are constructed directly. We also provide a general recursive construction for perfect difference packings, and as its applications, we obtain extensive recursive constructions for perfect difference families, some via incomplete perfect difference matrices with a regular hole. Examples of perfect difference packings directly constructed are used as ingredients in these recursive constructions to produce vast numbers of perfect difference families with block size 4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 415–449, 2010     

A Construction for Resolvable Designs and Its Generalizations

 In [14], D.K. Ray-Chaudhuri and R.M. Wilson developed a construction for resolvable designs, making use of free difference families in finite fields, to prove the asymptotic existence of resolvable designs with index unity. In this paper, generalizations of this construction are discussed. First, these generalizations, some of which require free difference families over rings in which there are some units such that their differences are still units, are used to construct frames, resolvable designs and resolvable (modified) group divisible designs with index not less than one. Secondly, this construction method is applied to resolvable perfect Mendelsohn designs. Thirdly, cardinalities of such sets of units are investigated. Finally, composition theorems for free difference families via difference matrices are described. They can be utilized to produce some new examples of resolvable designs.     

Tabu Machine: A New Neural Network Solution Approach for Combinatorial Optimization Problems

A new artificial neural network solution approach is proposed to solve combinatorial optimization problems. The artificial neural network is called the Tabu Machine because it has the same structure as the Boltzmann Machine does but uses tabu search to govern its state transition mechanism. Similar to the Boltzmann Machine, the Tabu Machine consists of a set of binary state nodes connected with bidirectional arcs. Ruled by the transition mechanism, the nodes adjust their states in order to search for a global minimum energy state. Two combinatorial optimization problems, the maximum cut problem and the independent set problem, are used as examples to conduct a computational experiment. Without using overly sophisticated tabu search techniques, the Tabu Machine outperforms the Boltzmann Machine in terms of both solution quality and computation time.