A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively, be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl+min{p₁,p₂}) time, where p₁ and p₂ denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl,km}) and outperforms the time bounds O(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks.     

Note on maximal bisection above tight lower bound

In a graph G=(V,E), a bisection (X,Y) is a partition of V into sets X and Y such that |X|?|Y|?|X|+1. The size of (X,Y) is the number of edges between X and Y. In the Max Bisection problem we are given a graph G=(V,E) and are required to find a bisection of maximum size. It is not hard to see that ⌈|E|/2⌉ is a tight lower bound on the maximum size of a bisection of G.We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph G=(V,E) has a bisection of size at least ⌈|E|/2⌉+k, where k is the parameter. We show that this parameterized problem has a kernel with O(k²) vertices and O(k³) edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most O(k²) vertices and O(k³) edges.     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index

Variance based methods have assessed themselves as versatile and effective among the various available techniques for sensitivity analysis of model output. Practitioners can in principle describe the sensitivity pattern of a model Y=f(X₁,X₂,…,Xk) with k uncertain input factors via a full decomposition of the variance V of Y into terms depending on the factors and their interactions. More often practitioners are satisfied with computing just k first order effects and k total effects, the latter describing synthetically interactions among input factors. In sensitivity analysis a key concern is the computational cost of the analysis, defined in terms of number of evaluations of f(X₁,X₂,…,Xk) needed to complete the analysis, as f(X₁,X₂,…,Xk) is often in the form of a numerical model which may take long processing time. While the computational cost is relatively cheap and weakly dependent on k for estimating first order effects, it remains expensive and strictly k-dependent for total effect indices. In the present note we compare existing and new practices for this index and offer recommendations on which to use.     

Model-based mean square error estimators for k-nearest neighbour predictions and applications using remotely sensed data for forest inventories

New model-based estimators of the uncertainty of pixel-level and areal k-nearest neighbour (k_nn) predictions of attribute Y from remotely-sensed ancillary data X are presented. Non-parametric functions predict Y from scalar ‘Single Index Model’ transformations of X. Variance functions generated estimates of the variance of Y. Three case studies, with data from the Forest Inventory and Analysis program of the U.S. Forest Service, the Finnish National Forest Inventory, and Landsat ETM+ ancillary data, demonstrate applications of the proposed estimators. Nearly unbiased k_nn predictions of three forest attributes were obtained. Estimates of mean square error indicate that k_nn is an attractive technique for integrating remotely-sensed and ground data for the provision of forest attribute maps and areal predictions.     

A Generalization of a Random Walk Problem

Let X _1,X 2,… be i.i.d. random variables with P(X ₁=-k) ∈ (0,1) for some k ∈ N, S ₁=X ₁ +···+ X ₁. We derive an exact expression for the probability that a particle performing a simple random walk will never cross a given straight line, i.e., P(S_l > lα + β for some l ∈ N), where α ∈ [?k,k], β S 0 are rational. Further the exact distribution of sup {S_l /l|≥1} is obtained.     

The possible cardinalities of global secure sets in cographs

Let G=(V,E) be a graph. A global secure set SD⊆V is a dominating set which also satisfies a condition that |N[X]∩SD|≥|N[X]−SD| for every subset X⊆SD. The minimum cardinality of the global secure set in the graph G is denoted by γ_s(G). In this paper, we introduce the notion of γ_s-monotone graphs. The graph G is γ_s-monotone if, for every k∈{γ_s(G),γ_s(G)+1,…,n}, it has a global secure set of cardinality k. We will also present the results concerning the minimum cardinality of the global secure sets in the class of cographs.     

Solving genus zero Diophantine equations over number fields

Let K be a number field and F(X,Y) an absolutely irreducible polynomial of K[X,Y] such that the algebraic curve defined by the equation F(X,Y)=0 is rational. In this paper we present practical algorithms for the determination of all solutions of the Diophantine equation F(X,Y)=0 in algebraic integers of K.     

On one extreme value problem for entropy and error probability

The problem of determining both the maximum and minimum entropy of a random variable Y as well as the maximum absolute value of the difference between entropies of Y and another random variable X is considered under the condition that the probability distribution of X is fixed and the error probability (i.e., the probability of noncoincidence of random values of X and Y) is given. A precise expression for the minimum entropy of Y is found. Some conditions under which the entropy of Y takes its maximum value are pointed out. In other cases, some lower and upper bounds are obtained for the maximum entropy of Y as well as for the maximum absolute value of the difference between entropies of Y and X.     

Mutual information, variation, and Fano’s inequality

Some upper and lower bounds are obtained for the maximum of the absolute value of the difference between the mutual information |I(X; Y) ? I(X′; Y′)| of two pairs of discrete random variables (X, Y) and (X′, Y′) via the variational distance between the probability distributions of these pairs. In particular, the upper bound obtained here substantially generalizes and improves the upper bound of [1]. In some special cases, our upper and lower bounds coincide or are rather close. It is also proved that the lower bound is asymptotically tight in the case where the variational distance between (X, Y) and (X′ Y′) tends to zero.     

Topology Preservation Within Digital Surfaces

Given two connected subsets Y⊂X of the set of the surfels of a connected digital surface, we propose three equivalent ways to express Y being homotopic to X. The first characterization is based on sequential deletion of simple surfels. This characterization enables us to define thinning algorithms within a digital Jordan surface. The second characterization is based on the Euler characteristics of sets of surfels. This characterization enables us, given two connected sets Y⊂X of surfels, to decide whether Y is n-homotopic to X. The third characterization is based on the (digital) fundamental group.     

A minimum-area circuit forl-selection

We prove tight upper and lower bounds on the area of semelective, when-oblivious VLSI circuits for the problem ofl-selection. The area required to select thelth smallest ofn k-bit integers is found to be heavily dependent on the relative sizes ofl,k, andn. Whenl<2 ^k , the minimal area isA = Θ(minn,l(k-logl)). Whenl≥2 ^k ,A = Θ(2 ^k (logl-k + 1)).     

A note on computing set overlap classes

Let V be a finite set of n elements and F={X₁,X₂,…,Xm} a family of m subsets of V. Two sets Xi and Xj of F overlap if Xi∩Xj≠∅, Xj?Xi≠∅, and Xi?Xj≠∅. Two sets X,Y∈F are in the same overlap class if there is a series X=X₁,X₂,…,Xk=Y of sets of F in which each XiXi+1 overlaps. In this note, we focus on efficiently identifying all overlap classes in time. We thus revisit the clever algorithm of Dahlhaus [E. Dahlhaus, Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, J. Algorithms 36 (2) (2000) 205-240] of which we give a clear presentation and that we simplify to make it practical and implementable in its real worst case complexity. An useful variant of Dahlhaus's approach is also explained.     

An effective algorithm for string correction using generalized edit distances—I. Description of the algorithm and its optimality

This paper deals with the problem of estimating a transmitted string X_s from the corresponding received string Y, which is a noisy version of X_s. We assume that Y contains any number of substitution, insertion, and deletion errors, and that no two consecutive symbols of X_s were deleted in transmission. We have shown that for channels which cause independent errors, and whose error probabilities exceed those of noisy strings studied in the literature [12], at least 99.5% of the erroneous strings will not contain two consecutive deletion errors. The best estimate X⁺ of X_s is defined as that element of H which minimizes the generalized Levenshtein distance $\text{D(}\text{X}\text{Y}\text{)}$ between X and Y. Using dynamic programming principles, an algorithm is presented which yields X⁺ without computing individually the distances between every word of H and Y. Though this algorithm requires more memory, it can be shown that it is, in general, computationally less complex than all other existing algorithms which perform the same task.     

Extended rank analysis of covariance adjusting for local correlations

An implicit assumption in the classical analysis of covariance is that the relationship between the response variable Y and the covariable X is consistent across the support of X. This may not hold in general if the strength of the relationship between Y and X varies in different regions of the covariate space [Doksum, K., Blyth, S., Bradlow, E., Meng, X.-L., Zhao, H., 1994. Correlation curves as local measures of variance explained by regression. J. Amer. Statist. Assoc. 89 (426), 571-582]. In this paper, to cope with heterocorrelaticity nonparametrically, we propose an extended rank analysis of covariance by adjusting local tolerances and dividing the support of X into disjoint subintervals with substantial different correlations between Y and X. The results showed that the proposed method was flexible in model error distributions as well as changing local correlations between Y and X, while retaining relatively well empirical power in simulations.     

ε-Optimality for bicriteria programs and its application to minimum cost flows

A subsetS?X of feasible solutions of a multicriteria optimization problem is called ε-optimal w.r.t. a vector-valued functionf:X→Y \( \subseteq \) ? ^K if for allx∈X there is a solutionz _x∈S so thatf _k(z _x)≤(1+ε)f _k (x) for allk=1,...,K. For a given accuracy ε>0, a pseudopolynomial approximation algorithm for bicriteria linear programming using the lower and upper approximation of the optimal value function is given. Numerical results for the bicriteria minimum cost flow problem on NETGEN-generated examples are presented.     

Combinatorial methods for constructing bipartite uniform minimal quasicomplete graphs (symmetrical block designs)

Consideration was given to a specific family of bipartite graphs consisting of two disjoint subsets X and Y of vertices and characterized by that each vertex in X (Y) is connected to each of the remaining vertices in X (Y) by a unique path of length two passing through some vertex in Y (X). The prefix “quasi” reflects the fact that complete connection of the vertices is realized by paths of length two rather than by edges. The problem of constructing uniform minimal graphs with identical cardinalities of the subsets X and Y which is of practical interest for complex communication networks was discussed. It belongs to the class of combinatorial problems of construction of the so-called symmetrical block designs.     

Cumulative defect

We prove that if X is a finite code and s is an infinite word with 3 X-factorizations, then the rank r(X) of X is at most |X|−2. More generally, if X belongs to a certain family of codes and s has l⩾2 X-factorizations, then the rank is at most |X|−l+1.     

Conditionally isotone interval operators

Interval operatorsF for constructing inclusion monotone interval sequences by iteration methods are discussed. IfX ₁?X ₀ andX _k+1 :=F(X _k ,k=0,1,…, then for two types of operators—aK-and anN-operator-it can be proved thatX _k+1 ?X _k for allk. Also the speed of convergence of the interval sequence will be explored.     

Revealing causality between heterogeneous data sources with deep restricted Boltzmann machines

In a number of real life applications, scientists do not have access to temporal data, since budget for data acquisition is always limited. Here we challenge the problem of causal inference between groups of heterogeneous non-temporal observations obtained from multiple sources. We consider a family of probabilistic algorithms for causal inference based on an assumption that in case where X causes Y, P(X) and P(Y|X) are statistically independent. For a number of real world applications, deep learning methods were reported to achieve the most accurate empirical performance, what motivates us to use deep Boltzmann machines to approximate the marginal and conditional probabilities of heterogeneous observations as accurate as possible.We introduce a novel algorithm to infer causal relationships between blocks of variables. The proposed method was tested on a benchmark of multivariate cause-effect pairs. We show by our experiments that our method achieves the state-of-the-art empirical accuracy, and sometimes outperforms the state-of-the-art methods. An important part of our contribution is an application of the proposed algorithm to an original medical data set, where we explore relations between alimentary patters, human gut microbiome composition, and health status.