Search

Alternative design and analysis methods for screening experiments based on locating arrays are presented. The number of runs in a locating array grows logarithmically based on the number of factors, providing efficient methods for screening complex engineered systems, especially those with large numbers of categorical factors having different numbers of levels. Our analysis method focuses on levels of factors in the identification of important main effects and two-way interactions. We demonstrate the validity of our design and analysis methods on both well-studied and synthetic data sets and investigate both statistical and combinatorial properties of locating arrays that appear to be related to their screening capability.

A pair of planes, both projective or both affine, of the same order and on the same pointset are orthogoval if each line of one plane intersects each line of the other plane in at most two points. In this paper we prove new constructions for sets of mutually orthogoval planes, both projective and affine, and review known results that are equivalent to sets of more than two mutually orthogoval planes. We also discuss the connection between sets of mutually orthogoval planes and covering arrays., 20 pages

Attribute-based methods are inherently identity-less as authorization decisions are made in terms of attributes possessed by the subject rather than identity. However, anonymity against the system is not guaranteed when attribute distribution allows for the composition of a policy that few subjects can satisfy. An anonymizing array ensures that any assignment of values to t attributes that appears in the array appears at least r times. When an anonymizing array is used for subjects registered to a system and policies contain conjunctions of at most t attributes, the system cannot identify the subject using the policy to to gain authorization with greater than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{r}$$\end{document} probability. Anonymizing arrays are similar to covering arrays with higher coverage and constraints, but have an additional desired property, homogeneity, due to their application domain. In this paper, we develop constructions for anonymizing arrays and propose a post-optimization mechanism to reduce homogeneity.

Let $x$ and $y$ be words. We consider the languages whose words $z$ are those for which the numbers of occurrences of $x$ and $y$, as subwords of $z$, are the same (resp., the number of $x$'s is less than the number of $y$'s, resp., is less than or equal). We give a necessary and sufficient condition on $x$ and $y$ for these languages to be regular, and we show how to check this condition efficiently.

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. %Our framework divides the construction in two stages. 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. The algorithms developed outperform the currently best known methods when the number of components ranges from 20 to 60, the number of options for each ranges from 3 to 6, and $t$-way interactions are covered for $t\in \{5,6\}$. In some cases a reduction in the number of tests by more than $50\%$ is achieved.

Andrew Rajah posed at the Loops'11 Conference in Trest, Czech Republic, the following conjecture: Is every variety of loops that satisfies Moufang's theorem contained in the variety of Moufang loops? This paper is motivated by that problem. We give a partial answer to this question and present two types of Steiner loops, one that satisfies Moufang's theorem and another that does not, and neither is Moufang loop.

A combinatorial approach to compressive sensing based on a deterministic column replacement technique is proposed. Informally, it takes as input a pattern matrix and ingredient measurement matrices, and results in a larger measurement matrix by replacing elements of the pattern matrix with columns from the ingredient matrices. This hierarchical technique yields great flexibility in sparse signal recovery. Specifically, recovery for the resulting measurement matrix does not depend on any fixed algorithm but rather on the recovery scheme of each ingredient matrix. In this paper, we investigate certain trade-offs for signal recovery, considering the computational investment required. Coping with noise in signal recovery requires additional conditions, both on the pattern matrix and on the ingredient measurement matrices., Comment: 11 pages, 6 figures

International audience; We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among $n$ nodes, each request using $1/C$ of the bandwidth; and during the second period, there is all-to-all uniform traffic only among a subset $V$ of $v$ nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of ADMs) for any $n,v$ and $C=4$ and $C' \in \{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most $C$ edges and where furthermore it contains at most $C'$ edges of the complete graph on $v$ specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case.

We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time, there is all-to-all uniform traffic among $n$ nodes, each request using $1/C$ of the bandwidth; and during the second period, there is all-to-all uniform traffic only among a subset $V$ of $v$ nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of ADMs) for any $n,v$ and $C=4$ and $C' \in \{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most $C$ edges and where furthermore it contains at most $C'$ edges of the complete graph on $v$ specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case.

The problem of routing is unmanned aerial vehicles (UAVs) flying circular flight patterns equipped with directional antennas is considered. The active communication links are modelled as trigonometric functions of time.

A (K4−e)-design of order v+w embeds a given Steiner triple system if there is a subset of v points on which the graphs of the design induce the blocks of the original Steiner triple system. It has been established that w≥v/3, and that when equality is met, such a minimum embedding of an STS(v) exists, except when v=15. Equality only holds when v≡15,27(mod30). One natural question is: What is the smallest order w such that some STS(v) can be embedded into a (K4−e)-design of order v+w? We solve the problem for 7 of the 10 congruence classes modulo 30.

A (K4-e)-design on v+w points embeds a Steiner triple system (STS) if there is a subset of v points on which the graphs of the design induce the blocks of a STS. It is established that w⩾v/3, and that when equality is met that such a minimum embedding of an STS(v) exists, except when v=15.

The rooted triplet distance measures the structural dissimilarity of two phylogenetic trees or networks by counting the number of rooted trees with exactly three leaf labels that occur as embedded subtrees in one, but not both of them. Suppose that N_1 = (V_1,E_1) and N_2 = (V_2,E_2) are rooted phylogenetic networks over a common leaf label set of size λ, that N_i has level k_i and maximum in-degree d_i for i ∈ {1,2}, and that the networks' out-degrees are unbounded. Denote n = max(|V_1|,|V_2|), m = max(|E_1|,|E_2|), k = max(k_1,k_2), and d = max(d_1, d_2). Previous work has shown how to compute the rooted triplet distance between N_1 and N_2 in O(λlogλ) time in the special case k 1, no efficient algorithms are known; a trivial approach leads to a running time of Ω(n^7λ^3) and the only existing non-trivial algorithm imposes restrictions on the networks' in- and out-degrees (in particular, it does not work when non-binary nodes are allowed). In this paper, we develop two new algorithms that have no such restrictions. Their running times are O(n^2m + λ^3) and O(m + k^3d^3λ + λ^3), respectively. We also provide implementations of our algorithms and evaluate their performance in practice. This is the first publicly available software for computing the rooted triplet distance between unrestricted networks of arbitrary levels.

REACT is a distributed resource allocation protocol that computes a max-min allocation of airtime for mesh networks. The allocation adapts automatically to changes in local traffic load and in local network views. SALT, a new contention window tuning algorithm, ensures that each node secures the airtime allocated to it by REACT. REACT and SALT are extended to the multi-hop flow scenario with the introduction of a new airtime reservation algorithm. With a reservation in place, multi-hop TCP flows show increased throughput when running over SALT and REACT compared to running over 802.11 DCF. All results are obtained from experimentation on the w-iLab.t wireless network testbed in Belgium.