Fast Algorithm for Computing the Upper Endpoint of Sample Variance for Interval Data: Case of Sufficiently Accurate Measurements

When we have n results x₁,...,x_n of repeated measurement of the same quantity, the traditional statistical approach usually starts with computing their sample average E and their sample variance V. Often, due to the inevitable measurement uncertainty, we do not know the exact values of the quantities, we only know the intervals x_i of possible values of x₁ In such situations, for different possible values x_i∈ x_i, we get different values of the variance. We must therefore find the range V of possible values of V. It is known that in general, this problem is NP-hard. For the case when the measurements are sufficiently accurate (in some precise sense), it is known that we can compute the interval V in quadratic time O(n²). In this paper, we describe a new algorithm for computing V that requires time O(n log(n)) (which is much faster than O(n²)).     

On the system of word equations x i 1 x i 2…x i m=y i 1 y i 2…y i n (i=1, 2, …) in a free monoid

 It is proved that the system of word equations x ⁱ ₁=y ⁱ ₁ y ⁱ ₂…y ⁱ _n , i=1, 2,…, ⌈n/2⌉ +1, has only cyclic solutions. Some sharpenings concerning the cases n=5, 7 and n≥9 are derived as well as results concerning the general system of equations x ⁱ ₁ x ⁱ ₂…x ⁱ _m =y ⁱ ₁ y ⁱ ₂…y ⁱ _n , i=1, 2,… . Applications to test sets of certain bounded languages are considered. Received: 18 May 1995/2 January 1996     

Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

The determinantal complexity of a polynomial f(x ₁,x ₂,…,x _n ) is the minimum m such that f=det  _m (L(x ₁,x ₂,…,x _n )), where L(x ₁,x ₂,…,x _n ) is a matrix whose entries are affine forms in the x _i s over some field $\mbox {$\mbox {.     

On weighted P‐quantile aggregation

We consider the problem of aggregating ordinal information with quantitative or qualitative importance based on quantile operations. For a bag 〈x₁, x₂, …, x_n〉 in real or in (finite) ordinal scales, the quantile operations used in this paper are operating based on the floating position index of x_i that is determined by its position on the ordered sequence (x₍₁₎, x₍₂₎, …, x_(n)), where x_(i) is the ith smallest element of the bag 〈x₁, x₂, …, x_n〉. We call this type of quantile aggregation as the floating position index‐based quantile (p‐quantile) aggregation. We study on weighted p‐quantile aggregation in real scales and extend the corresponding techniques to p‐quantile aggregation of ordinal information with quantitative importance. The aggregated result of the latter is represented by a general ordinal proportional 2‐tuple. On basis of the notion of importance transformation (that is modified from Yager), we investigate p‐quantile aggregation of ordinal information with qualitative importance. Then, we use p‐quantile aggregation to define the floating position index‐based ordered weighted averaging (P‐OWA) aggregation of ordinal information with qualitative importance and apply it to the problem of multicriteria decision making. © 2008 Wiley Periodicals, Inc.     

Panconnectivity of Cartesian product graphs

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d _G (x,y)≤ℓ≤n−1, where d _G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q _n (k ₁,k ₂,…,k _n ) is panconnected if and only if k _i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube Q³_nQ^{3}_{n} is panconnected.     

Exact Upper Bound on the Mean of the Product of Many Random Variables with Known Expectations

In practice, in addition to the intervals x _i = [x _i , x _i] of possible values of inputs x ₁, ..., x _n, we sometimes also know their means E _i. For such cases, we provide an explicit exact (= best possible) upper bound for the mean of the product x ₁ ... x _n of positive values x _i.     

Interpolazione con splines verificanti una opportuna condizione

Summary A partition of the interval [x ₀,x _n+1] inton+1 subintervals [x _i ,x _i+1] (i=0,1,...,n) is considered. A spline functionf(x)∈C ^m , which coincides with a polynomialp _i (x)[p _i (x _i )=y _i ,p _i (x _i+1)=y _i+1] of degreem+1 in [x _i ,x _i+1 ], is introduced. Such a spline depends onm arbitrary constants. These constants are determined minimizing the integral .      

Windows scheduling of arbitrary-length jobs on multiple machines

The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I=〈(w ₁,ℓ ₁),(w ₂,ℓ ₂),…,(w _n ,ℓ _n )〉 of n pairs of positive integers that are associated with the jobs 1,2,…,n, respectively. The processing length of job i is ℓ _i slots where a slot is the processing time of one unit of length. The goal is to repeatedly and non-preemptively schedule all the jobs on the fewest possible machines such that the gap (window) between two consecutive beginnings of executions of job i is at most w _i slots. This problem arises in push broadcast systems in which data are transmitted on multiple channels. The problem is NP-hard even for unit-length jobs and a (1+ε)-approximation algorithm is known for this case by approximating the natural lower bound W(I)=?_i=1ⁿ(1/w_i)W(I)=\sum_{i=1}^{n}(1/w_{i}). The techniques used for approximating unit-length jobs cannot be extended for arbitrary-length jobs mainly because the optimal number of machines might be arbitrarily larger than the generalized lower bound W(I)=?_i=1ⁿ(l_i/w_i)W(I)=\sum_{i=1}^{n}(\ell_{i}/w_{i}). The main result of this paper is an 8-approximation algorithm for the WS problem with arbitrary lengths using new methods, different from those used for the unit-length case. The paper also presents another algorithm that uses 2(1+ε)W(I)+logw _max machines and a greedy algorithm that is based on a new tree representation of schedules. The greedy algorithm is optimal for some special cases, and computational experiments show that it performs very well in practice.     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P ₁=〈u ₁,u ₂,…,u _n 〉 and P ₂=〈v ₁,v ₂,…,v _n 〉 of G are said to be independent if u ₁=v ₁, u _n =v _n , and u _i ≠v _i for all 1<i<n; and both are full-independent if u _i ≠v _i for all 1≤i≤n. Moreover, P ₁ and P ₂ are independent starting at u ₁, if u ₁=v ₁ and u _i ≠v _i for all 1<i≤n. A set of Hamiltonian paths {P ₁,P ₂,…,P _k } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u ₁) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u ₁). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q _n is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q _n . In this paper, we show the following results:

A quadratic-time algorithm for smoothing interval functions

In many real-life applications, physical considerations lead to the necessity to consider the smoothest of all signals that is consistent with the measurement results. Usually, the corresponding optimization problem is solved in statistical context. In this paper, we propose a quadratic-time algorithm for smoothing aninterval function. This algorithm, givenn+1 intervals x₀, ..., x _n with 0 ∈ x₀ and 0 ∈ x _n , returns the vectorx ₀, ...,x _n for whichx ₀=x ₀=0,x _i ∈ x _i , and Σ(x _i+1?x _i )² → min.     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group

LetG andH be graphs with |V(G)≤ |V(H)|. Iff:V(G) →V(H) is a one-to-one map, we letdilation(f) be the maximum of dist _H (f x),f(y)) over all edgesxy inG where dist _H denotes distance inH. The construction of maps fromG toH of small dilation is motivated by the problem of designing small slowdown simulations onH of algorithms that were originally designed for the networkG. LetS(n), thestar network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent ifx o (1,i) =y for somei. That is,xy is an edge ifx andy are related by a transposition involving some fixed symbol (which we take to be 1). Also letP(n), thepancake network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent if one can be obtained from the other by reversing some prefix. That is,xy is an edge ifx andy are related byx o (1,i(2,i-1) ⋯ ([i/2], [i/2]) =y. The star network (introduced in [AHK]) has nice symmetry properties, and its degree and diameter are sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube network. These advantages ofS(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube. The concern of this paper is to construct low dilation maps of hypercube networks into star or pancake networks. Typically in such problems, there is a tradeoff between keeping the dilationsmall and simulating alarge hypercube. Our main result shows that at the cost ofO (1) dilation asn→ ∞, one can embed a hypercube of near optimum dimension into the star or pancake networksS(n) orP(n). More precisely, lettingQ (d) be the hypercube of dimensiond, our main theorem is stated below. For simplicity, we state it only in the special case when the star network dimension is a power of 2. A more general result (applying to star networks of arbitrary dimension) is obtained by a simple interpolation. This author's research was done during the Spring Semester 1991, as a visiting professor in the Department of Mathematics and Statistics at Miami University.     

New Results on Noncommutative and Commutative Polynomial Identity Testing

Using ideas from automata theory, we design the first polynomial deterministic identity testing algorithm for the sparse noncommutative polynomial identity testing problem. Given a noncommuting black-box polynomial f ? \mathbb F{x₁,?,x_n}f \in {\mathbb F}\{x_{1},\ldots,x_n\} of degree d with at most t monomials, where the variables x_i are noncommuting, we give a deterministic polynomial identity test that checks if C o 0C \equiv 0 and runs in time polynomial in d, n, |C|, and t. Our algorithm evaluates the black-box polynomial for x_i assigned to matrices over \mathbbF{\mathbb{F}} and, in fact, reconstructs the entire polynomial f in time polynomial in n, d and t.     

Why clustering in function approximation? Theoretical explanation

Function approximation is a very important practical problem: in many practical applications, we know the exact form of the functional dependence y=f(x₁,…,x_n) between physical quantities, but this exact dependence is complicated, so we need a lot of computer space to store it, and a lot of time to process it, i.e., to predict y from the given x_i. It is therefore necessary to find a simpler approximate expression g(x₁,…,x_n)≈f(x₁,…,x_n) for this same dependence. This problem has been analyzed in numerical mathematics for several centuries, and it is, therefore, one of the most thoroughly analyzed problems of applied mathematics. There are many results related to approximation by polynomials, trigonometric polynomials, splines of different type, etc. Since this problem has been analyzed for so long, no wonder that for many reasonable formulations of the optimality criteria, the corresponding problems of finding the optimal approximations have already been solved. Lately, however, new clustering‐related techniques have been applied to solve this problem (by Yager, Filev, Chu, and others). At first glance, since for most traditional optimality criteria, optimal approximations are already known, the clustering approach can only lead to non‐optimal approximations, i.e., approximations of inferior quality. We show, however, that there exist new reasonable criteria with respect to which clustering‐based function approximation is indeed the optimal method of function approximation. © 2000 John Wiley & Sons, Inc.     

Computing median and antimedian sets in median graphs

The median (antimedian) set of a profile π=(u ₁,…,u _k ) of vertices of a graph G is the set of vertices x that minimize (maximize) the remoteness ∑ _i d(x,u _i ). Two algorithms for median graphs G of complexity O(n idim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes.     

Optimal strategies against a liar

We consider the following scenario: There are two individuals, say Q (Questioner) and R (Responder), involved in a search game. Player R chooses a number, say x, from the set S={1,…,M}. Player Q has to find out x by asking questions of type: “which one of the sets A₁,A₂,…,A_q, does x belong to?”, where the sets A₁,…,A_q constitute a partition of S. Player R answers “i” to indicate that the number x belongs to A_i. We are interested in the least number of questions player Q has to ask in order to be always able to correctly guess the number x, provided that R can lie at most e times. The case e=0 obviously reduces to the classical q-ary search, and the necessary number of questions is [log_qM]. The case q=2 and e1 has been widely studied, and it is generally referred to as Ulam's game. In this paper we consider the general case of arbitrary q2. Under the assumption that player R is allowed to lie at most twice throughout the game, we determine the minimum number of questions Q needs to ask in order to successfully search for x in a set of cardinality M=qⁱ, for any i1. As a corollary, we obtain a counterexample to a recently proposed conjecture of Aigner, for the case of an arbitrary number of lies. We also exactly solve the problem when player R is allowed to lie a fixed but otherwise arbitrary number of times e, and M=qⁱ, with i not too large with respect to q. For the general case of arbitrary M, we give fairly tight upper and lower bounds on the number of the necessary questions.     

Automating Pólya Theory: The Computational Complexity of the Cycle Index Polynomial

In this paper we investigate the computational difficulty of evaluating and approximately evaluating Pólya′s cycle index polynomial. We start by investigating the difficulty of determining a particular coefficient of the cycle index polynomial. In particular, we consider the following problem, in which i is taken to be a fixed positive integer: Given a set of generators for a permutation group G whose degree, n, is a multiple of i, determine the coefficient of x^n/i_i in the cycle index polynomial of G. We show that this problem is #P-hard for every fixed i >1. Next, we consider the evaluation problem. Let y₁, y₂, ... stand for an arbitrary fixed sequence of non-negative real numbers. The cycle index evaluation problem that is associated with this sequence is the following: Given a set of generators for a degree n permutation group G, evaluate the cycle index polynomial of G at the point (y₁, ..., y_n). We show that if there exists an i such that y_i ≠ yⁱ₁ and y_i ≠ 0 then the evaluation problem associated with y₁, y₂, ..., is #P-hard. We observe that the evaluation problem is solvable in polynomial time if y_j = y^j₁ for every positive integer j and that it is solvable in polynomial time if y_j = 0 for every integer j >1. Finally, we consider the approximate evaluation problem. We show that it is NP-hard to approximately solve the evaluation problem if there exists an i such that y_i > yⁱ₁. Furthermore, we show that it is NP-hard to approximately solve the evaluation problem if y₁ = y₂ = ··· = y for some positive non-integer y. We derive some corollaries of our results which deal with the computational difficulty of counting equivalence classes of combinatorial structures.     

Border Correlations of Partial Words

Partial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ?’s. Setting $A_{\diamond}=A\cup\lbrace{\diamond}\rbracePartial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ⋄’s. Setting A_à=Aè{à}A_{\diamond}=A\cup\lbrace{\diamond}\rbrace , A _⋄ ^* denotes the set of all partial words over A. In this paper, we investigate the border correlation function b:A_à^*?{a,b}^*\beta:A_{\diamond}^{*}\rightarrow\lbrace a,b\rbrace^{*} that specifies which conjugates (cyclic shifts) of a given partial word w of length n are bordered, that is, β(w)=c ₀ c ₁…c _n−1 where c _i =a or c _i =b according to whether the ith cyclic shift σ ⁱ (w) of w is unbordered or bordered. A partial word w is bordered if a proper prefix x ₁ of w is compatible with a proper suffix x ₂ of w, in which case any partial word x containing both x ₁ and x ₂ is called a border of w. In addition to β, we investigate an extension β′:A _⋄ ^*→ℕ^* that maps a partial word w of length n to m ₀ m ₁…m _n−1 where m _i is the length of a shortest border of σ ⁱ (w). Our results extend those of Harju and Nowotka.