For an ordering of the blocks of a design, the point sum of an element is the sum of the indices of blocks containing that element. Block labelling for popularity asks for the point sums to be as ...equal as possible. For Steiner systems of order
v
and strength
t
in general, the average point sum is
O
(
v
2
t
-
1
)
; under various restrictions on block partitions of the Steiner system, the difference between the largest and smallest point sums is shown to be
O
(
v
(
t
+
1
)
/
2
log
v
)
. Indeed for Steiner triple systems, direct and recursive constructions are given to establish that systems exist with all point sums equal for more than two thirds of the admissible orders.
For a consecutive ordering of the edges of a graph
G
=
(
V
,
E
)
, the point sum of a vertex is the sum of the indices of edges incident with that vertex. Motivated by questions of balancing accesses ...in data placements in the presence of popularity rankings, an edge ordering is egalitarian when all point sums are equal, and almost egalitarian when two point sums differ by at most 1. It is established herein that complete graphs on
n
vertices admit an egalitarian edge ordering when
n
≡
1
,
2
,
3
(
mod
4
)
and
n
∉
{
3
,
5
}
, or an almost egalitarian edge ordering when
n
≡
0
(
mod
4
)
and
n
≠
4
.
Covering perfect hash families represent certain covering arrays compactly. Applying two probabilistic methods to covering perfect hash families improves upon the asymptotic upper bound for the ...minimum number of rows in a covering array with
v
symbols,
k
columns, and strength
t
. One bound can be realized by a randomized polynomial time construction algorithm using column resampling, while the other can be met by a deterministic polynomial time conditional expectation algorithm. Computational results are developed for both techniques. Further, a random extension algorithm further improves on the best known sizes for covering arrays in practice. An extensive set of computations with column resampling and random extension yields explicit constructions when
k
≤
75
for strength seven,
k
≤
200
for strength six,
k
≤
600
for strength five, and
k
≤
2500
for strength four. When
v
>
3
, almost all known explicit constructions are improved upon. For strength
t
=
3
, restrictions on the covering perfect hash family ensure the presence of redundant rows in the covering array, which can be removed. Using restrictions and random extension, computations for
t
=
3
and
k
≤
10
,
000
again improve upon known explicit constructions in the majority of cases. Computations for strengths three and four demonstrate that a conditional expectation algorithm can produce further improvements at the expense of a larger time and storage investment.
A variety of probabilistic notions of network reliability of graphs and digraphs have been proposed and studied since the early 1950s. Although grounded in the engineering and logistics of network ...design and analysis, the research also spans pure and applied mathematics, with connections to areas as diverse as combinatorics and graph theory, combinatorial enumeration, optimization, probability theory, real and complex analysis, algebraic topology, commutative algebra, the design and analysis of algorithms, and computational complexity. In this paper we describe the landscape of various notions of network reliability, the roads well traveled, and some that appear likely to lead to meaningful and important journeys.
Software behavior depends on many factors. Combinatorial testing (CT) aims to generate small sets of test cases to uncover defects caused by those factors and their interactions. Covering array ...generation, a discrete optimization problem, is the most popular research area in the field of CT. Particle swarm optimization (PSO), an evolutionary search-based heuristic technique, has succeeded in generating covering arrays that are competitive in size. However, current PSO methods for covering array generation simply round the particle's position to an integer to handle the discrete search space. Moreover, no guidelines are available to effectively set PSOs parameters for this problem. In this paper, we extend the set-based PSO, an existing discrete PSO (DPSO) method, to covering array generation. Two auxiliary strategies (particle reinitialization and additional evaluation of gbest) are proposed to improve performance, and thus a novel DPSO for covering array generation is developed. Guidelines for parameter settings both for conventional PSO (CPSO) and for DPSO are developed systematically here. Discrete extensions of four existing PSO variants are developed, in order to further investigate the effectiveness of DPSO for covering array generation. Experiments show that CPSO can produce better results using the guidelines for parameter settings, and that DPSO can generate smaller covering arrays than CPSO and other existing evolutionary algorithms. DPSO is a promising improvement on PSO for covering array generation.
Modern software systems often consist of many different components, each with a number of options. Although unit tests may reveal faulty options for individual components, functionally correct ...components may interact in unforeseen ways to cause a fault. Covering arrays are used to test for interactions among components systematically. A two‐stage framework, providing a number of concrete algorithms, is developed for the efficient construction of covering arrays. In the first stage, a time and memory efficient randomized algorithm covers most of the interactions. In the second stage, a more sophisticated search covers the remainder in relatively few tests. In this way, the storage limitations of the sophisticated search algorithms are avoided; hence, the range of the number of components for which the algorithm can be applied is extended, without increasing the number of tests. Many of the framework instantiations can be tuned to optimize a memory‐quality trade‐off, so that fewer tests can be achieved using more memory.
Covering arrays have been widely used to detect the presence of faults in large software and hardware systems. Indeed, finding failures that result from faulty interactions requires that all ...interactions that may cause faults be covered by a test case. However, finding the actual faults requires more, because the failures resulting from two potential sets of faults must not be the same. The combinatorial requirements on test suites to enable a tester to locate the faults are developed, and set in the context of similar combinatorial search questions. Test suites known as locating and detecting arrays to locate faults both in principle and in practice generalize covering arrays, thereby addressing combinatorial fault characterization. In common with covering arrays, these locating and detecting arrays scale logarithmically in size with the number of factors, but unlike covering arrays they support complete characterization of the interactions that underlie faults.
The maximum independence number of Steiner triple systems of order v is well‐known. Motivated by questions of access balancing in storage systems, we determine the maximum total cardinality of a pair ...of disjoint independent sets of Steiner triple systems of order v for all admissible orders.
We use deterministic and probabilistic methods to analyze the performance of compressed sensing matrices constructed from Hadamard matrices and pairwise balanced designs, previously introduced by a ...subset of the authors. In this paper, we obtain upper and lower bounds on the sparsity of signals for which our matrices guarantee recovery. These bounds are tight to within a multiplicative factor of at most √4 2. We provide new theoretical results and detailed simulations, which indicate that the construction is competitive with Gaussian random matrices, and that recovery is tolerant to noise. A new recovery algorithm tailored to the construction is also given.
In this paper, topology-transparent scheduling for mobile multi-hop wireless networks is extended from constant-weight to variable-weight schedules. A construction of variable-weight ...topology-transparent schedules – the first of its kind – is provided based on transversal designs from the finite field. The schedules are integrated into the VWATT medium access control (MAC) protocol, enabling nodes to dynamically select their schedule weights to accommodate both their local traffic load and local topology while maintaining a guarantee on maximum delay. Simulations show VWATT to increase throughput compared to constant-weight topology-transparent schedules, to reduce both maximum and expected delay relative to schedules whose weights are not constrained to the set of weights, and to adapt rapidly to changes in topology and traffic load. The results suggest variable-weight topology-transparent scheduling as a viable approach to medium access control when a bound on delay is required.
PDF
