Using integer programming techniques for the solution of an experimental design problem

Latin hypercube sampling is often used to estimate the distribution function of a complicated function of many random variables. In so doing, it is typically necessary to choose a permutation matrix which minimizes the correlation among the cells in the hypercube layout. This problem can be formulated as a generalized, multi-dimensional assignment problem. For the two-dimensional case, we provide a polynomial algorithm. For higher dimensions, we offer effective heuristic and bounding procedures.Supported in part by a grant from the National Institute of Standards and Technology (60NANB9D-0974).Supported in part by grants from the Office of Naval Research (N00014-90-J-1324) and the Air Force Office of Scientific Research (F49 620-90-C-0022).Research partially performed while visiting the Department of Mathematics, Brunel University, Uxbridge, England.     

LJUNGSKILE: a program for assessing uncertainties in speciation calculations

Speciation calculations are often the base upon which further and more important conclusions are drawn, e.g., solubilities and sorption estimates used for retention of hazardous materials. Since speciation calculations are based on experimentally determined stability constants of the relevant chemical reactions, the measurement and experimental uncertainty in these constants will affect the reliability of the simulation output. The present knowledge of the thermodynamic data relevant for predicting the behaviour of a complex chemical system is quite heterogeneous. In order to predict the impact of these uncertainties on the reliability of a simulation output requires sophisticated modelling codes. In this paper, we will present a computer program, LJUNGSKILE, which utilises the thermodynamic equilibrium code PHREEQC to statistically calculate uncertainties in speciation based on uncertainties in stability constants. A short example is included.     

n维超立方体的层次结构模型

本文首次提出了 n维超立方体的层次结构模型 HHC,详细讨论了该结构中结点的分布及各结点的连接关系 .并利用 HHC,讨论了超立方体非对称比较模型的最优诊断算法 ,极大独立点集等问题     

Cycles embedding on folded hypercubes with faulty nodes

Let F_Fv$F{F}_v$ be the set of faulty nodes in an n$n$-dimensional folded hypercube F_Qn$F{Q}_n$ with |F_Fv|≤n−2$\left|F{F}_v\right|\le n-2$. In this paper, we show that if n≥3$n\ge 3$, then every edge of F_Qn−F_Fv$F{Q}_n-F{F}_v$ lies on a fault-free cycle of every even length from 4$4$ to 2ⁿ−2|F_Fv|$2^n-2\left|F{F}_v\right|$, and if n≥2$n\ge 2$ and n$n$ is even, then every edge of F_Qn−F_Fv$F{Q}_n-F{F}_v$ lies on a fault-free cycle of every odd length from n+1$n+1$ to 2ⁿ−2|F_Fv|−1$2^n-2\left|F{F}_v\right|-1$.     

Decomposing a graph into expanding subgraphs

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that any graph is close to being the disjoint union of expanders. Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. Three examples of our results are the following:

• A classical result of Lipton, Rose and Tarjan from 1979 states that if is a hereditary family of graphs and every graph in has a vertex separator of size , then every graph in has O(n) edges. We construct a hereditary family of graphs with vertex separators of size such that not all graphs in the family have O(n) edges.
• Trevisan and Arora‐Barak‐Steurer have recently shown that given a graph G, one can remove only 1% of its edges to obtain a graph in which each connected component has good expansion properties. We show that in both of these decomposition results, the expansion properties they guarantee are essentially best possible, even when one is allowed to remove 99% of G's edges.
• Sudakov and the second author have recently shown that every graph with average degree d contains an n‐vertex subgraph with average degree at least and vertex expansion . We show that one cannot guarantee a better vertex expansion even if allowing the average degree to be O(1).

The above results are obtained as corollaries of a new family of graphs which we construct in this paper. These graphs have a super‐linear number of edges and nearly logarithmic girth, yet each of their subgraphs has (optimally) poor expansion properties.     

An improved averaged two-replication procedure with Latin hypercube sampling

The averaged two-replication procedure assesses the quality of a candidate solution to a stochastic program by forming point and confidence interval estimators on its optimality gap. We present an improved averaged two-replication procedure that uses Latin hypercube sampling to form confidence intervals of optimality gap. This new procedure produces tighter and less variable interval widths by reducing the sampling error by $\sqrt{2}$. Despite having tighter intervals, it improves an earlier procedure’s asymptotic coverage probability bound from ${(1?\alpha )}^2$ to $(1?\alpha )$.     

Spherical and Clockwise Spherical Graphs

The main subject of our study are spherical (weakly spherical) graphs, i.e. connected graphs fulfilling the condition that in each interval to each vertex there is exactly one (at least one, respectively) antipodal vertex. Our analysis concerns properties of these graphs especially in connection with convexity and also with hypercube graphs. We deal e.g. with the problem under what conditions all intervals of a spherical graph induce hypercubes and find a new characterization of hypercubes: G is a hypercube if and only if G is spherical and bipartite.     

Mbius立方体的拓扑结构性质

超立方体网络是目前在超级计算机处理器结构中应用得最广泛的拓扑结构,Mbius立方体是超立方体的一种变形,已经被证明它在某些方面具有优于超立方体的拓扑性质.本文指出了n维Mbius立方体递归结构的一些重要拓扑性质.     

Load balancing in the parallel optimization of block-angular linear programs

Decomposition algorithms for block-angular linear programs give rise to a natural, coarse-grained parallelism that can be exploited by processing the subproblems concurrently within a distributed-memory environment. The parallel efficiency of the distributed approach, however, is critically dependent on the duration of the inherently serial master phase relative to that of the bottleneck subproblem. This paper investigates strategies for improving efficiency in distributed Dantzig—Wolfe decomposition by better balancing the load between the master and subproblem processors. We report computational experience on an Intel iPSC/2 hypercube multiprocessor with test problems having dimensions up to about 30 000 rows, 87 000 columns, and 200 coupling constraints.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

Scrambling Sobol' and Niederreiter–Xing Points

Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. In particular, randomized (0, m, s)-nets in basebproduce unbiased estimates of the integral, have a variance that tends to zero faster than 1/nfor any square integrable integrand and have a variance that for finitenis never more thane?2.718 times as large as the Monte Carlo variance. Lower bounds thaneare known for special cases. Some very important (t, m, s)-nets havet>0. The widely used Sobol' sequences are of this form, as are some recent and very promising nets due to Niederreiter and Xing. Much less is known about randomized versions of these nets, especially ins>1 dimensions. This paper shows that scrambled (t, m, s)-nets enjoy the same properties as scrambled (0, m, s)-nets, except the sampling variance is guaranteed only to be belowb^t[(b+1)/(b−1)]^stimes the Monte Carlo variance for a least-favorable integrand and finiten.