Wrap-Around L2-Discrepancy of Random Sampling, Latin Hypercube and Uniform Designs

For comparing random designs and Latin hypercube designs, this paper con- siders a wrap-around version of the L₂-discrepancy (WD). The theoretical expectation and variance of this discrepancy are derived for these two designs. The expectation and variance of Latin hypercube designs are significantly lower than those of the corresponding random designs. We also study construction of the uniform design under the WD and show that one-dimensional uniform design under this discrepancy can be any set of equidistant points. For high dimensional uniform designs we apply the threshold accepting heuristic for finding low discrepancy designs. We also show that the conjecture proposed by K. T. Fang, D. K. J. Lin, P. Winker, and Y. Zhang (2000, Technometrics) is true under the WD when the design is complete.     

Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets

This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result of this paper says that for a given n, any sufficiently large hypercube contains a hamiltonian path or cycle with prescribed n edges just when the family of the edges satisfies certain natural necessary conditions. Analogous results are presented for dense sets. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Constructing Covering Codes with Given Automorphisms

Let K(n,r) denote the minimum cardinality of a binary covering code of length n and covering radius r. Constructions of covering codes give upper bounds on K(n,r). It is here shown how computer searches for covering codes can be sped up by requiring that the code has a given (not necessarily full) automorphism group. Tabu search is used to find orbits of words that lead to a covering. In particular, a code D found which proves K(13,1) 704, a new record. A direct construction of D given, and its full automorphism group is shown to be the general linear group GL(3,3). It is proved that D is a perfect dominating set (each word not in D is covered by exactly one word in D) and is a counterexample to the recent Uniformity Conjecture of Weichsel.     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

Scrambling non-uniform nets

In this paper, we consider Owen’s scrambling of an (m−1, m, d)-net in base b which consists of d copies of a (0, m, 1)-net in base b, and derive an exact formula for the gain coefficients of these nets. This formula leads us to a necessary and sufficient condition for scrambled (m − 1, m, d)-nets to have smaller variance than simple Monte Carlo methods for the class of L ₂ functions on [0, 1] ^d . Secondly, from the viewpoint of the Latin hypercube scrambling, we compare scrambled non-uniform nets with scrambled uniform nets. An important consequence is that in the case of base two, many more gain coefficients are equal to zero in scrambled (m − 1, m, d)-nets than in scrambled Sobol’ points for practical size of samples and dimensions.      

Random random walks on ℤ2 d

Summary. We consider random walks on classes of graphs defined on the d-dimensional binary cube ℤ₂ ^d by placing edges on n randomly chosen parallel classes of vectors. The mixing time of a graph is the number of steps of a random walk before the walk forgets where it started, and reaches a random location. In this paper we resolve a question of Diaconis by finding exact expressions for this mixing time that hold for all n>d and almost all choices of vector classes. This result improves a number of previous bounds. Our method, which has application to similar problems on other Abelian groups, uses the concept of a universal hash function, from computer science.     

Study and modelling of two apple quality attributes: the soluble solids content and the firmness

Recently, the basic dynamics of fruit characteristics have been modelled using a stochastic approach. The time evolution of apple quality attributes was represented by means of a system of differential equations in which the initial conditions and model parameters are both random. In this work, a complete study of two apple quality attributes, the soluble solids content and the firmness, is carried out. For each of these characteristics, the system of differential equations is linear and the state variables and the parameters are represented as random variables with their statistical properties (mean values, variances, covariances, joint probability density function) known at the initial time. The dynamic behaviour of these statistical properties is analysed. The variance propagation algorithm is used to obtain an analytical expression of the dynamic behaviour of the mean value, the variance, the covariance and the probability density function. A Monte Carlo method and the Latin hypercube method were developed to obtain a numerical expression of the dynamic behaviour of these statistical quantities and particularly to follow the time evolution of joint probability density function which represents one but the best mean to characterize random phenomena linked with fruit quality attributes.     

On k‐detour subgraphs of hypercubes

A spanning subgraph G of a graph H is a k‐detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k‐detour subgraphs of the n‐dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k‐detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k‐detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008     

Convex excess in partial cubes

The convex excess ce(G) of a graph G is introduced as where the summation goes over all convex cycles of G. It is proved that for a partial cube G with n vertices, m edges, and isometric dimension i(G), inequality 2n?m?i(G)?ce(G)≤2 holds. Moreover, the equality holds if and only if the so‐called zone graphs of G are trees. This answers the question from Bre r et al. [Tiled partial cubes, J Graph Theory 40 (2002) 91–103] whether partial cubes admit this kind of inequalities. It is also shown that a suggested inequality from Bre r et al. [Tiled partial cubes, J Graph Theory 40 (2002) 91–103] does not hold. Copyright © 2011 John Wiley & Sons, Ltd.     

Finding maximin latin hypercube designs by Iterated Local Search heuristics

The maximin LHD problem calls for arranging N points in a k-dimensional grid so that no pair of points share a coordinate and the distance of the closest pair of points is as large as possible. In this paper we propose to tackle this problem by heuristic algorithms belonging to the Iterated Local Search (ILS) family and show through some computational experiments that the proposed algorithms compare very well with different heuristic approaches in the established literature.