Bipartite Locating Array

As a special case of experimental design,locating array is useful for locating interaction faults in component-based systems.In this paper,bipartite locating array is proposed to locate interaction faults between two specific groups.Such arrays are especially suitable for antagonism tests.Based on the definition of bipartite locating array,the lower bound on run sizes are established to measure the optimality for specific parameters.When a single fault is to be located,optimal bipartite locating arrays are proved to be equivalent to certain specific combinatorial configurations.As a result,approaches to constructing optimal bipartite locating arrays are proposed and some infinite classes of optimal bipartite locating arrays are obtained using the corresponding construction met hod.     

On a Combinatorial Framework for Fault Characterization

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 equivalence between optimal detecting arrays and super-simple OAs

The notion of a detecting array (DTA) was proposed, recently, by Colbourn and McClary in their research on software interaction tests. Roughly speaking, testing with a (d, t)−DTA(N, k, v) can locate d interaction faults and detect whether there are more than d interaction faults. In this paper, we establish a general lower bound on sizes of DTAs and explore an equivalence between optimal DTAs and super-simple orthogonal arrays (OAs). Taking advantage of this equivalence, a great number of DTAs are constructed, which are all optimal in the sense of their sizes. In particular, an optimal (2, t)−DTA(N, 5, v) of strength t = 2 or 3 is shown to exist whenever v ≥ 3 excepting (t, v) ? {(2, 3), (2, 6),(3, 4), (3, 6)}{(t, v) \in \{(2, 3), (2, 6),(3, 4), (3, 6)\}} .     

Detecting arrays and their optimality

Detecting arrays were proposed by Colbourn and McClary in 2008, which are of interest in generating software test suites to cover all t-sets of component interactions and detect interaction faults in component-based systems. So far, optimality and constructions of detecting arrays have not been studied systematically. Indeed, no useful benchmark to measure the optimality of detecting arrays has previously been given, and only some sporadic examples of optimal detecting arrays have been found. This paper tries to take the first step by presenting a lower bound on the size of detecting arrays and some methods of constructing optimal detecting arrays. A number of infinite series of optimal detecting arrays are then obtained.     

Quasistability of a Vector Trajectory Majority Optimization Problem

We consider a multicriteria combinatorial problem with majority optimality principle whose particular criteria are of the form MINSUM, MINMAX, and MINMIN. We obtain a lower attainable bound for the radius of quasistability of such a problem in the case of the Chebyshev norm on the space of perturbing parameters of the vector criterion. We give sufficient conditions for the quasistability of the problem; these are also necessary in the case of linear special criteria.     

Combinatorial theorems about embedding trees on the real line

We consider the combinatorial problem of embedding the metric defined by an unweighted graph into the real line, so as to minimize the distortion of the embedding. This problem is inspired by connections to Banach space theory and to computer science. After establishing a framework in which to study line embeddings, we focus on metrics defined by three specific families of trees: complete binary trees, fans, and combs. We construct asymptotically optimal (i.e., distortion‐minimizing) line embeddings for these metrics and prove their optimality via suitable lower bound arguments. It appears that even such specialized metrics require nontrivial constructions and proofs of optimality require sophisticated combinatorial arguments. The combinatorial techniques from our work might prove useful in further algorithmic research on low distortion metric embeddings. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 153–168, 2011     

Constructing strength three covering arrays with augmented annealing

A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays.     

Optimal locating arrays for at most two faults

Locating arrays are of interest in generating software test suites to cover all t-way component interactions and locate interaction faults in component-based systems.Recently,Tang,Colbourn and Yin made an investigation into optimal locating arrays in the case where a single fault is to be located.They pointed out that when two or more faults were considered,matters would become rather complicated.To handle those cases generally seems challenging,but is well worth further research.In this paper,we establish a lower bound on the size of locating arrays with at most two faults,and then prove that optimal locating arrays meeting this bound can be equivalently characterized in terms of orthogonal arrays with prescribed properties.Using this characterization,we develop a number of constructions of optimal locating arrays.Two infinite series of optimal locating arrays are then obtained.     

混水平均匀设计的构造

我们用离散偏差来度量部分因子设计的均匀性,本文的目的在于寻找一些构造混水平均匀设计的方法,这些方法比文献中已有的方法更简单且计算成本更低.我们得到了离散偏差的一个下界,如果一个U 型设计的离散偏差值达到这个下界,那么该设计是—个均匀设计.我们建立了均匀设计与组合设计理论中一致可分解设计之间的联系.通过一致可分解设计,我们提出了一些构造均匀设计的新方法,同时也给出了许多均匀设计存在的无穷类.     

Smoke and mirrors: Combinatorial properties of small cardinals equiconsistent with huge cardinals

Since the work of Godel and Cohen many questions in infinite combinatorics have been shown to be independent of the usual axioms for mathematics, Zermelo Frankel Set Theory with the Axiom of Choice (ZFC). Attempts to strengthen the axioms to settle these problems have converged on a system of principles collectively known as Large Cardinal Axioms.These principles are linearly ordered in terms of consistency strength. As far as is currently known, all natural independent combinatorial statements are equiconsistent with some large cardinal axiom. The standard techniques for showing this use forcing in one direction and inner model theory in the other direction.The conspicuous open problems that remain are suspected to involve combinatorial principles much stronger than the large cardinals for which there is a current fine-structural inner model theory for.The main results in this paper show that many standard constructions give objects with combinatorial properties that are, in turn, strong enough to show the existence of models with large cardinals are larger than any cardinal for which there is a standard inner model theory.     

On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.     

Extremal plane stochastic matrices of dimension three

We examine combinatorial properties of extremal plane stochastic matrices of dimension three. Methods are given for the construction of such extremal matrices of any order. We obtain a lower bound for the number of connected extremal matrices of order n and conclude with some open problems.     

A nonconvex quadratic optimization approach to the maximum edge weight clique problem

The maximum edge weight clique (MEWC) problem, defined on a simple edge-weighted graph, is to find a subset of vertices inducing a complete subgraph with the maximum total sum of edge weights. We propose a quadratic optimization formulation for the MEWC problem and study characteristics of this formulation in terms of local and global optimality. We establish the correspondence between local maxima of the proposed formulation and maximal cliques of the underlying graph, implying that the characteristic vector of a MEWC in the graph is a global optimizer of the continuous problem. In addition, we present an exact algorithm to solve the MEWC problem. The algorithm is a combinatorial branch-and-bound procedure that takes advantage of a new upper bound as well as an efficient construction heuristic based on the proposed quadratic formulation. Results of computational experiments on some benchmark instances are also presented.     

Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.     

Finding lower bounds on the complexity of secret sharing schemes by linear programming

Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants.By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.     

Solving chance-constrained combinatorial problems to optimality

The aim of this paper is to provide new efficient methods for solving general chance-constrained integer linear programs to optimality. Valid linear inequalities are given for these problems. They are proved to characterize properly the set of solutions. They are based on a specific scenario, whose definition impacts strongly on the quality of the linear relaxation built. A branch-and-cut algorithm is described to solve chance-constrained combinatorial problems to optimality. Numerical tests validate the theoretical analysis and illustrate the practical efficiency of the proposed approach.     

Branching from the largest upper bound Folklore and facts

Branch-and-bound algorithms are widely used to solve combinatorial maximization problems. At each step of such an algorithm a search strategy selects an active subset of feasible solutions for examination. In this paper we discuss the formal properties and the practical value of search strategies based on branching from the largest upper bound (BLUB strategies). We investigate conditions under which BLUB strategies are optimal in the sense that they minimize the number of subsets generated. Counterexamples show that the conditions given in the literature are not strong enough and a correct optimality condition is formulated. Finally, we argue that the practical objections raised against BLUB strategies are not necessarily convincing.     

Model-adaptive optimal discretization of stochastic integrals*

We study the optimal discretization error of stochastic integrals driven by a multidimensional continuous Brownian semimartingale. In the previous works a pathwise lower bound for the renormalized quadratic variation of the error was provided together with an asymptotically optimal discretization strategy, i.e. for which the lower bound is attained. However the construction of the optimal strategy involved the knowledge about the diffusion coefficient of the semimartingaleunder study. In this work we provide a model-adaptive asymptotically optimal discretization strategy that does not require any prior knowledge about the model. We prove the optimality for quite general class of discretization strategies based on kernel techniques for adaptive estimation and previously obtained optimal strategies that use random ellipsoid hitting times.     

Coercivity and image of constrained extremum problems

The concept of coercivity is extended to the image space, and it is exploited to obtain a lower bound for the minimum of a constrained extremum problem and a sufficient condition for the optimality. Problems which are coercive in the image space turn out to have zero duality gap. A possible application to variational inequalities is illustrated by means of an example.     

The Minimum Number of Basic Feasible Solutions to a Transport Problem

In this paper, combinatorial arguments are used to derive a lower bound to the number of basic feasible solutions of a transport problem. A separate argument is given for degenerate and non-degenerate systems, and an example which attains the lower bound is given for each type.