Performance bounds for binary testing with arbitrary weights

Summary Binary testing concerns finding good algorithms to solve the class of binary identification problems. A binary identification problem has as input a set of objects, including one regarded as distinguished (e.g., faulty), for each object an a priori estimate that it is the distinguished object, and a set of tests. Output is a testing procedure to isolate the distinguished object. One seeks minimal cost testing procedures where cost is the average cost of isolation, summed over all objects. This is a problem schema for the diagnosis problem: applications occur in medicine, systematic biology, machine fault location, quality control and elsewhere.In this paper we extend work of Garey and Graham to assess the capability of a fast approximation rule, the binary splitting rule, to give near optimal testing procedures when the a priori estimates are arbitrary. We find conditions on the test set such that the approximation error reduces nearly to that of the equally likely a priori estimate case of Garey and Graham and find another upper bound on approximation error for the same test set conditions which works very well under a priori estimate assumptions where the first result is poor.This research has been partially supported by AFOSR, Air Force Command, AFOSR-81-0221 and by the Rockland Research Center, Rockland, NY, USA     

Lower bounds on the rotation distance of binary trees

The rotation distanced(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T. While it is known that d(S,T)?2n−6, a well-known conjecture states that there are trees for which this bound is sharp for any value of n?11. We are unable to prove the conjecture, but we give here some simple criteria for lower bound evaluation, leading for example to individuate some “regular” tree structures for which d(S,T)=3n/2−O(1), or d(S,T)=5n/3−O(1).     

Performance bounds for nonhomogeneous queues

This paper considers nonhomogeneous M(t)/M(t)1 queues which can model systems such as communications networks. For such systems, bounds on moment-generating functions and on the tail distribution of the queue process are obtained. These bounds are useful for characterizing the quality of service a system can provide to its users. An approach utilizing the theory of differential equations is adapted. The bounds given in this paper are tighter than those previously available. In fact, the bounds can be made arbitrarily tight given sufficient computational effort     

A note on the Bernstein algorithm for bounds for interval polynomials

In computing the range of values of a polynomial over an intervala≤x≤b one may use polynomials of the form $$\left( {\begin{array}{*{20}c} k \\ j \\ \end{array} } \right)\left( {x - a} \right)^j \left( {b - x} \right)^{k - j} $$ called Bernstein polynomials of the degreek. An arbitrary polynomial of degreen may be written as a linear combination of Bernstein polynomials of degreek≥n. The coefficients of this linear combination furnish an upper/lower bound for the range of the polynomial. In this paper a finite differencelike scheme is investigated for this computation. The scheme is then generalized to interval polynomials.     

一种网络延迟精确控制的调度算法

在网络数据传输调度中，基于最早时限优先（EDF）的算法具有单点最优的延迟界限控制能力。现有的各种EDF改进算法，主要着眼于提供延迟上界的保证能力，而当采用机顶盒之类的缓冲能力较弱的设备作为客户终端时，还需要网络提供精确的延迟下界控制能力。在原有EDF改进算法的基础上提出了精确延迟界控制的最早时限优先算法。该算法不但能同时保证延迟上界和下界，还使得节点可以独立地决定为数据流分配的缓冲区大小，并增加了节点允许抖动量的取值范围，从而提高了节点数据的转发效率。     

Efficient algorithm for computing QFT bounds

This article presents an efficient algorithm for computing quantitative feedback theory (QFT) bounds for frequency-domain specifications from plant templates which are approximated by a finite number of points. To develop the algorithm, an efficient procedure is developed for testing, at a given frequency, whether or not a complex point lies in the QFT bound. This test procedure is then utilised along with a pivoting procedure to trace out, with a prescribed accuracy or resolution, the boundary of the QFT bound. The developed algorithm for computing QFT bounds has the advantages that it is efficient and can compute QFT bounds with multi-valued boundaries. A numerical example is given to show the computational superiority of the proposed algorithm.     

New bounds for binary covering arrays using simulated annealing

Covering arrays (CAs) are combinatorial structures specified as a matrix of N rows and k columns over an alphabet on v symbols such that for each set of t columns (called the strength of the array) every t-tuple of symbols is covered. Recently they have been used to represent interaction test suites for software testing given that they provide economical sized test cases while still preserving important fault detection capabilities.This paper introduces an improved implementation of a simulated annealing algorithm, called ISA, for constructing CAs of strengths three through six over a binary alphabet (i.e., binary CAs). Extensive experimentation is carried out, using 127 well-known benchmark instances, for assessing its performance with respect to an existing simulated annealing implementation, a greedy method, and five state-of-the-art algorithms. The results show that our algorithm attains 104 new bounds and equals the best-known solutions for the other 23 instances consuming reasonable computational time. Furthermore, the implications of using these results as ingredients to recursive constructions are also analyzed.     

Performance bounds for estimation under uncertainty

For the class of linear Gauss-Markov systems with binary parameters uncertainty, the minimum variance estimate of the state and associated covariance of error expressions were derived in a closed form in [1, 2]. In this paper expressions for the conditional and unconditional covariances of error matrices are presented for the M-ary case. Useful upper and lower bounds for the unconditional covariance of error are also presented which are valid, on the average, for any measurement sequence. A geophysical seismic data filtering example applying these results is also given.     

Performance bounds for rate envelope multiplexing

In QoS guaranteed communication networks, such as ATM, several classes of traffic streams with widely varying characteristics share common transmission resources. To achieve high utilization of these networks, while providing appropriate grade of service for all connections, the development of powerful traffic management algorithms is a central issue. Due to scalability reasons traffic control functions like flow, congestion and admission control often need simple and efficient characterization of traffic using mainly aggregate characteristics instead of using information about all the individual flows. In this paper, the saturation probability as a possible performance measure of aggregate traffic on a communication link is discussed. This performance metric, also referred to as the tail distribution of aggregate traffic, is essential in traffic control and management algorithms of high-speed networks including also the prospective QoS Internet. In this paper, using the Chernoff bounding method, efficient closed-form bounds have been derived for the saturation probability for the case when little information is available on the aggregate traffic. The performance of these estimates is also shown by means of numerical examples.     

New theoretical bounds on the aperiodic correlation functions of binary sequences

In order to reduce or eliminate the multiple access interference in code division multiple access (CDMA) systems, we need to design a set of spreading sequences with good autocorrelation functions (ACF) and crosscorrelation functions (CCF). The importance of the spreading codes to CDMA systems cannot be overemphasized, for the type of the code used, its length, and its chip rate set bounds on the capability of the system that can be changed only by changing the code. Several new lower bounds which are stronger than the well-known Sarwate bounds, Welch bounds and Levenshtein bounds for binary sequence set with respect to the spreading sequence length, family size, maximum aperiodic autocorrelation sidelobe and maximum aperiodic crosscorrelation value are established.     

Lower bounds for testing Euclidean Minimum Spanning Trees

The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G=(P,E) on a set of points in the two-dimensional plane is a minimum spanning tree with respect to the Euclidean distance. Czumaj et al. [A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] gave a 1-sided-error non-adaptive property-tester for this task of query complexity . We show that every non-adaptive (not necessarily 1-sided-error) property-tester for this task has a query complexity of , implying that the test in [A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] is of asymptotically optimal complexity. We further prove that every adaptive property-tester has query complexity of Ω(n1/3). Those lower bounds hold even when the input graph is promised to be a bounded degree tree.     

Estimating error bounds for tensor product binary subdivision volumetric model

In this article, by generalizing the techniques of Mustafa, Falai and Deng (2006), we estimate the error bounds between the tensor product binary volumetric model and its control polyhedron after k-fold subdivision. Our bounds are expressed in terms of the first-order differences of the initial control point sequences and constants that depend on the subdivision masks.     

A domain splitting algorithm for parabolic problems

In the parallel implementation of solution methods for parabolic problems one has to find a proper balance between the parallel efficiency of a fully explicit scheme and the need for stability and accuracy which requires some degree of implicitness. As a compromise a domain splitting scheme is proposed which is locally implicit on slightly overlapping subdomains but propagates the corresponding boundary data by a simple explicit process. The analysis of this algorithm shows that it has satisfactory stability and approximation properties and can be effectively parallelized. These theoretical results are confirmed by numerical tests on a transputer system.     

Exponential bounds for the random walk algorithm on random planted 3-SAT

Random walk algorithm （RWalkSAT） is one of the simplest and oldest heuristics for satisfiability problems. In contrast to many experimental results, relatively few rigorous analyses of RWalkSAT are available. Up to now, runtime results of small density random 3-SAT have been achieved showing RWalkSAT terminates successfully in linear time up to clause density 1.63. This paper presents a rigorous runtime analysis of RWalkSAT for 3-CNF formulas generated under the planted assignment distribution. It proves that with overwhelming probability, when starting from any initial assignment ｜x｜ 0.9999n, the expected number of steps until RWalkSAT on random planted formulas with a large constant density finds the planted assignment （1, . . . ,1） is at least Ω（1.1514n） and at most O（n21.1517n）.     

求解Ramsey数下界的模拟退火算法

对于图G_1、G_2,2色广义Ramsey数R(G_1,G_2)是指最小正整数P,使得每一个p阶的图G,或者G包含G_1,或者G的补图包含G_2。用改进的模拟退火算法求解得到了R(W_m,K_n),R(B_m,K_n),R(F_m,K_n),类型的一些Ramsey数的下界。     

Performance bounds for queues via generating functions

Modern applications, e.g., very large-scale integration (VLSI) manufacturing, give rise to complicated queueing models, often of the re-entrant type. Their complexity, together with implications of their performance, have renewed interest in their performance and the computation of good control (e.g., scheduling) policies. Recent work concentrated on computable (mostly linear) performance bounds. We show that the linear bounds can be obtained naturally, and under weaker assumptions, using generating function techniques. This approach gives rise to a new class of bounds, on performance over busy periods     

Performance bounds for coprime factor controller reductions

This paper investigates the performance of coprime factor based controller reduction methods. We show that under some mild conditions closed-loop performance bounds can be derived for observer-based controllers. The results in this paper lay a mathematical foundation for using coprime factor controller reduction methods in certain classes of controller reduction problems.     

Performance bounds for concurrent software with rendezvous

Synchronous message-passing communication, or rendezvous, occurring between software tasks can have a significant effect on system performance. The rendezvous style of communication is coming into wider use in programming languages and operating systems for parallel and distributed environments. Understanding the performance implications of this style of inter-task communication is becoming a matter of practical importance. The dual nature of a task which acts both like a customer as well as a server, makes the performance analysis of rendezvous-based multitasking systems quite different from the analysis of the other queueing systems with known results. This research focuses on rendezvous-based systems in which the execution behavior of the software has a nondeterministic component of a very general nature which may for example be the manifestation of a data dependent behavior. Based on a model called the Stochastic Rendezvous Network the computation of bounds on task throughputs for multitasking systems characterized by rendezvous style communication is presented. Although the behavior of tasks is called stochastic, it is very general and the results are valid for general distributions of computation times and the number of messages generated by tasks. The inter-relationship among task throughputs, however, makes it difficult to extract the bounds in closed analytic form. The notion of a feasible throughput region which encloses the set of feasible tasks throughputs and captures the inter-relationship among the behavior of tasks is introduced. Variations of this basic bounding approach that are useful in the context of different types of multitasking systems are considered in the article. For example, a novel technique based on interval arithmetic is proposed for the computation of numerical values for the bounds. The applicability of the bounds and their tightness are analyzed through case studies. Issues such as the inter-relationship between the software architecture and system performance, and the effect of processor contention on the performance bounds are discussed.     

Performance and stability bounds for dynamic networks

In this work, we study the impact of dynamically changing link capacities on the delay bounds of LIS (Longest-In-System) and SIS (Shortest-In-System) protocols on specific networks (that can be modelled as Directed Acyclic Graphs (DAGs)) and stability bounds of greedy contention–resolution protocols running on arbitrary networks under the Adversarial Queueing Theory. Especially, we consider the model of dynamic capacities  , where each link capacity may take on integer values from [1,C]$[1,C]$ with C>1$C>1$, under a (w,ρ)$(w,\rho )$-adversary. We show that the packet delay on DAGs for LIS is upper bounded by O(iwρC)$O(\mathit{iw}\rho C)$ and lower bounded by Ω(iwρC)$\Omega (\mathit{iw}\rho C)$ where i   is the level of a node in a DAG (the length of the longest path leading to node v$v$ when nodes are ordered by the topological order induced by the graph). In a similar way, we show that the performance of SIS on DAGs is lower bounded by Ω(iwρC)$\Omega (\mathit{iw}\rho C)$, while the existence of a polynomial upper bound for packet delay on DAGs when SIS is used for contention–resolution remains an open problem. We prove that every queueing network running a greedy contention–resolution protocol is stable for a rate not exceeding a particular stability threshold, depending on C and the length of the longest path in the network.