Recently, covering arrays have been the subject of considerable research attention as they hold both theoretical interest and practical importance due to their applications to testing. In this thesis, we perform the first comprehensive study of a generalization of covering arrays called variable strength covering arrays, where we dictate the interactions to be covered in the array by modeling them as facets of an abstract simplicial complex. We outline the necessary background in the theory of hypergraphs, combinatorial testing, and design theory that is relevant to the study of variable strength covering arrays. We then approach questions that arise in variable strength covering arrays in a number of ways. We demonstrate their connections to hypergraph homomorphisms, and explore the properties of a particular family of abstract simplicial complexes, the qualitative independence hypergraphs. These hypergraphs are tightly linked to variable strength covering arrays, and we determine and identify several of their important properties and subhypergraphs. We give a detailed study of constructions for variable strength covering arrays, and provide several operations and divide-and-conquer techniques that can be used in building them. In addition, we give a construction using linear feedback shift registers from primitive polynomials of degree 3 over arbitrary finite fields to find variable strength covering arrays, which we extend to strength-3 covering arrays whose sizes are smaller than many of the best known sizes of covering arrays. We then give an algorithm for creating variable strength covering arrays over arbitrary abstract simplicial complexes, which builds the arrays one row at a time, using a density concept to guarantee that the size of the resultant array is asymptotic in the logarithm of the number of facets in the abstact simplicial complex. This algorithm is of immediate practical importance, as it can be used to create test suites for combinatorial testing. Finally, we use the Lovasz Local Lemma to nonconstructively determine upper bounds on the sizes of arrays for a number of different families of hypergraphs. We lay out a framework that can be used for many hypergraphs, and then discuss possible strategies that can be taken in asymmetric problems.

No description available.

Regular Coverings - Structure and Complexity Michaela Seifrtová The thesis consists of two main parts, the first concentrated on the struc- ture of graph coverings, where different properties of regular graph coverings are presented, and the second dealing with computational complexity of the covering problem. Favorable results have been achieved in this area, proving the problem is solvable in polynomial time for all graphs whose order is a prime multiple of the order of the covered graph. 1

In practice, graphs often occur as perturbed product structures, so-called approximate graph products. The practical application of the well-known prime factorization algorithms is therefore limited, since most graphs are prime, although they can have a product-like structure. This work is concerned with the strong graph product. Since strong product graphs G contain subgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to develop local approaches that cover a graph by factorizable patches and then use this information to derive the global factors. First, we investigate the local structure of strong product graphs and introduce the backbone B(G) of a graph G and the so-called S1-condition. Both concepts play a central role for determining the prime factors of a strong product graph in a unique way. Then, we discuss several graph classes, in detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear time prime factorization algorithms. Combining these results, we then derive a new local prime factorization algorithm for all graphs. Finally, we discuss approximate graph products. We use the new local factorization algorithm to derive a method for the recognition of approximate graph products. Furthermore, we evaluate the performance of this algorithm on a sample of approximate graph products.

<p>This thesis is devoted to introducing new problem formulations and exact solution methods for a class of continuous covering location models. The manuscript includes three self-contained studies which are organized as in the following. </p> <p> In the first study, we introduce the planar expropriation problem with non-rigid rectangular facilities which has many applications in regional planning and undesirable facility location domains. This model is proposed for determining the locations and formations of two-dimensional rectangular facilities. Based on the geometric properties of such facilities, we developed a new formulation which does not require employing distance measures. The resulting model is a mixed integer nonlinear program. For solving this new model, we derived a continuous branch-and-bound framework utilizing linear approximations for the tradeoff curve associated with the facility formation alternatives. Further, we developed new problem generation and bounding strategies suitable for this particular branch-and-bound procedure. We designed a computational study where we compared this algorithm with two well-known mixed integer nonlinear programming solvers. Computational experience showed that the branch-and-bound procedure we developed performs better than BARON and SBB both in terms of processing time and size of the branching tree.</p> <p> The second study is referred to as the planar maximal covering problem with single convex polygonal shapes and it has ample applications in transmitter location, inspection of geometric shapes and directional antenna location. In this study, we investigated maximal point containment by any convex polygonal shape in the Euclidean plane. Using a fundamental separation property of convex sets, we derived a mixed integer linear formulation for this problem. We were able to identify two types of special cuts based on the geometric properties of the shapes under study, which were later employed for developing a branch-and-cut procedure for solving this particular location model. We also evaluated the resultant bound quality after employing the afore-mentioned cuts. </p> <p> In the third study, we discuss the dynamic planar expropriation problem with single convex polygonal shapes. We showed how the basic problem formulations discussed in the first two studies extend to their diametric opposites, and further to models in higher dimensions. Subsequently, we allowed a dynamic setting where the shape under study is expected to function over a finite planning horizon and the system parameters such as the fixed point locations and expropriation costs are subject to change. The shape was permitted to relocate at the beginning of each time period according to particular relocation costs. We showed that this dynamic problem structure can be decomposed into a set of static problems under a particular vector of relocations. We discussed the solution of this model by two enumeration procedures. Subsequently, we derived an incomplete dynamic programming procedure which is suitable for this distinct problem structure. In this method, there is no need to evaluate all the branches of the branching tree and one proceeds with keeping the minimum stage cost. The evaluation of a branch is postponed until relocation takes place in the lower-level problems. With this postponing structure, the procedure turned out to be superior to the two enumeration procedures in terms of tree size. </p> / Thesis / Doctor of Philosophy (PhD)

This thesis focuses on algorithms solving the on-line Bin-Covering problem, when the items are generated from a known, stationary distribution. We introduce the Prospect Algorithm. The main idea behind the Prospect Algorithm is to use information on the item distribution to estimate how easy it will be to fill a bin with small overfill as a function of the empty space left in it. This estimate is then used to determine where to place the items, so that all active bins either stay easily fillable, or are finished with small overfill. We test the performance of the algorithm by simulation, and discuss how it can be modified to cope with additional constraints and extended to solve the Bin-Packing problem as well. The Prospect Algorithm is then adapted to achieve perfect packing, yielding a new version, the Prospect+ Algorithm, that is a slight but consistent improvement. Next, a Markov Decision Process formulation is used to obtain an optimal Bin-Covering algorithm to compare with the Prospect Algorithm. Even though the optimal algorithm can only be applied to limited (small) cases, it gives useful insights that lead to another modification of the Prospect Algorithm. We also discuss two relaxations of the on-line constraint, and describe how algorithms that are based on solving the Subset-Sum problem are used to tackle these relaxed problems. Finally, several practical issues encountered when using the Prospect Algorithm in the real-world are analyzed, a computationally efficient way of doing the background calculations needed for the Prospect Algorithm is described, and the three versions of the Prospect Algorithm developed in this thesis are compared.

Thesis (MScEng)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: All structures are designed for a particular set of load combinations. For roof structures the critical loading combinations are predominantly wind actions. The accumulative effect of wind actions, by wind entering through dominant openings to exert pressure on the inside of roof structures together with the suction of wind vortices on the outside of the roof, can contribute to extreme load combinations. Frequently recorded failures on roof structures suggest that either the loads are underestimated or the resisting capacity of the roof coverings is overestimated. The focus of this study is directed on the latter, determining the effective resistance of roof coverings in the form of sheeting against a Uniformly Distributed Load (UDL) such as wind actions. To determine the carrying capacity of a roofing structure, the standard approach used involves experimental tests on certain configurations with two or more spans. The structural test set-up is loaded with sandbags until failure is reached. For the design of roofing systems, design tables are used that list the maximum allowable purlin spacing. The purlin spacing is presented in the form of a fixed value in units of length and is shown independent of a UDL that the roof needs to be designed for. The need to a new approach to determining the resistance of roof covering systems was identified. The resistance of roof coverings for the Ultimate Limit State (ULS) and the Serviceability Limit State (SLS) depends on a number of parameters such as the bending resistance, the stiffness of the sheeting in bending and the carrying capacity of the fastening system. To evaluate these structural parameters, experimental tests were performed. A full-scale experimental test setup, capable of simulating a UDL on roof sheeting, was developed. The experimental test set-up consists of four different configurations, each specifically schematized to evaluate a certain structural design parameter. The magnitude of the structural design parameters depends on the applied UDL and the span length, which is the distance between consecutive supports of the sheeting system. Therefore, by using the structural design parameters determined experimentally, a set of design tables could be generated. The design tables produce the maximum allowable span length of a roofing system that uses a desired UDL as a variable. By using the design tables, the purlin spacing for any roof structure can be calculated given its design loading combination. The calculated purlin spacings are now a function of the basic parameters that determine the resistance of the roof sheeting. / AFRIKAANSE OPSOMMING: Geen opsomming

Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.

In this paper, the study of k-fold branched coverings for which the branch set is a stratified set is considered. First of all, the existence of universal k-fold branched coverings over CW-complexes with stratified branch set is proved using Brown's Representability Theorem. Next, an explicit construction of universal k-fold branched coverings over manifolds is given. Finally, some homotopy and homology groups are computed for some specific examples of Universal k-fold branched coverings.

Steganography is a science which is interested in communication hiding. This work is focused on the most recent methods related to this topic. Mainly, it is matrix embedding, which uses coding theory, and sum and difference covering sets (SDCS). Rainbow coloring of grid graphs is used to receive even better results. This technique decrease amplitude of performed changes. It makes stegosystems less likely to be detected. Properties which describe behavior of each stegosystem are included for each technique. 1