Derivative based global sensitivity measures and their link with global sensitivity indices

A model function f(x₁,…,x_n) defined in the unit hypercube Hⁿ with Lebesque measure dx = dx₁…dx_n is considered. If the function is square integrable, global sensitivity indices provide adequate estimates for the influence of individual factors x_i or groups of such factors. Alternative estimators that require less computer time can also be used. If the function f is differentiable, functionals depending on ∂f/∂x_i have been suggested as estimators for the influence of x_i. The Morris importance measure modified by Campolongo, Cariboni and Saltelli μ  * is an approximation of the functional μi=_∫Hn|∂f/∂xi|dx${\mu }_i={\int }_{H^n}\left|\partial f\text{/}\partial x_i\right|dx$.     

Subdivision methods for solving polynomial equations

This paper presents a new algorithm for solving a system of polynomials, in a domain of Rⁿ${\mathbb{R}}^n$. It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule  . We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of Rⁿ${\mathbb{R}}^n$. The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem.     

Stratification associated with local b-functions

The local b$b$-function _bf,p(s)$b_{f,p}\left(s\right)$ of an n$n$-variate polynomial f∈C[x]$f\in \mathbb{C}\left[x\right]$ (x=(_x1,…,_xn)$x=(x_1,\dots ,x_n)$) at a point p∈Cⁿ$p\in {\mathbb{C}}^n$ is constant on each stratum of a stratification of Cⁿ${\mathbb{C}}^n$. We propose a new method for computing such a stratification and _bf,p(s)$b_{f,p}\left(s\right)$ on each stratum. In the existing method proposed in Oaku (1997b), a primary ideal decomposition of an ideal in C[x,s]$\mathbb{C}[x,s]$ is needed and our experiment shows that the primary decomposition can be a bottleneck for computing the stratification. In our new method, the computation can be done by just computing ideal quotients and examining inclusions of algebraic sets. The precise form of a stratum can be obtained by computing the decomposition of the radicals of the ideals in C[x]$\mathbb{C}\left[x\right]$ defining the stratum. We also introduce various techniques for improving the practical efficiency of the implementation and we show results of computations for some examples.     

An exact exponential time algorithm for counting bipartite cliques

We present a simple exact algorithm for counting bicliques of given size in a bipartite graph on n   vertices. We achieve running time of O(1.2491ⁿ)$O({1.2491}^n)$, improving upon known exact algorithms for finding and counting bipartite cliques.     

Minimax regret 1-sink location problem in dynamic cycle networks

In this paper, we consider the minimax regret 1-sink location problem in a dynamic cycle network with positive edge lengths and uniform edge capacity. Let C be an undirected cycle graph of n vertices and n edges. Each edge has a positive edge length and a uniform edge capacity. Each vertex has a weight which is not known exactly but we know the interval it belongs to. The problem is to find a point x as the sink on the cycle and all weights evacuate to x   such that the maximum regret for all possible weight distributions is minimized. This paper presents an O(n³log?n)$O(n^3\log ?n)$ time algorithm.     

A note on order statistics-based parametric pattern classification

Recently, a novel classification paradigm is proposed, named Classification by Moments of Order Statistics (CMOS), which is shown to attain the optimal Bayesian bound for symmetric distributions and a near-optimal accuracy for asymmetric distributions 13 and 9. However, in the process of deriving the order statistics-based classification scheme, the authors use a plausible relation “E[Φ(_xk,n)]=k/(n+1)?E[_xk,n]=Φ⁻¹(k/(n+1))$E\left[\Phi \right(x_{k,n}\left)\right]=k/(n+1)?E\left[x_{k,n}\right]={\Phi }^{-1}(k/(n+1\left)\right)$”, where Φ$\Phi$ is the cumulative distribution function of random variable X$X$, and _xk,n$x_{k,n}$ is the k-th order statistics of a sample of size n from X. Therefore, the new approach actually should be viewed as the classification scheme based on the percentiles of distribution, instead of the so-called order statistics-based classification. In this paper, we will build the CMOS using 2-OS criteria in its true sense. Furthermore, we show that the order statistics-based classification reaches the optimal Bayesian bound for symmetric distributions, and compare the accuracy of CMOS, Bayesian classification, median-based classifier and percentiles-based classification for non-symmetric distributions. The theoretical results are verified by rigorous experiments as well.     

Optimal fault-tolerant embedding of paths in twisted cubes

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let _TQn(V,E)${\mathit{TQ}}_n(V,E)$ denote the n-dimensional twisted cube. We prove that a path of length l   can be embedded between any two distinct nodes with dilation 1 for any faulty set F⊂V(_TQn)∪E(_TQn)$F\subset V({\mathit{TQ}}_n)\cup E({\mathit{TQ}}_n)$ with |F|?n-3$\left|F\right|?n-3$ and any integer l   with 2^n-1-1?l?|V(_TQn-F)|-1$2^{n-1}-1?l?|V({\mathit{TQ}}_n-F)|-1$ (n?3$n?3$). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l   and faulty set size |F|$\left|F\right|$ for a successful embedding are tight. That is, the result does not hold if l?2^n-1-2$l?2^{n-1}-2$ or |F|?n-2$\left|F\right|?n-2$. We also extend the result on (n-3)$(n-3)$-Hamiltonian connectivity of _TQn${\mathit{TQ}}_n$ in the literature.     

Digital Steiner sets and Matheron semi-groups

There are various ways to define digital convexity in Zⁿ$Z^n$. The proposed approach focuses on structuring elements (and not the sets under study), whose digital versions should allow to construct hierarchies of operators satisfying Matheron semi-groups law _γλγμ=_γmax(λ,_μ)${\gamma }_{\lambda }{\gamma }_{\mu }={\gamma }_{\max (\lambda \text{,}\mu )}$, where λ$\lambda$ is a size factor. In Rⁿ$R^n$ the convenient class is the Steiner one. Its elements are Minkowski sums of segments. We prove that it admits a digital equivalent when the segments of Zⁿ$Z^n$ are Bezout. The conditions under which the Steiner sets are convex in Zⁿ$Z^n$, and are connected, are established. The approach is then extended to structuring elements that vary according to the law of perspective, and also to anamorphoses, so that the digital Steiner class and its properties can extend to digital spaces as a sphere or a torus.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

Optimum sweeps of simple polygons with two guards

A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P  , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n²)$O(n^2)$ time and O(n)$O(n)$ space algorithm for optimizing this metric, where n   is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n)$O(n)$.     

On triangulation axes of polygons

We propose the triangulation axis as an alternative skeletal structure for a simple polygon P. This axis is a straight-line tree that can be interpreted as an anisotropic medial axis of P, where inscribed disks are line segments or triangles. The underlying triangulation that specifies the anisotropy can be varied, to adapt the axis so as to reflect predominant geometrical and topological features of P. Triangulation axes typically have much fewer edges and branchings than the Euclidean medial axis or the straight skeleton of P. Still, they retain important properties, as for example the reconstructability of P   from its skeleton. Triangulation axes can be computed from their defining triangulations in O(n)$O(n)$ time. We investigate the effect of using several optimal triangulations for P  . In particular, careful edge flipping in the constrained Delaunay triangulation leads, in O(nlog?n)$O(n\log ?n)$ overall time, to an axis competitive to ‘high quality axes’ requiring Θ(n³)$\Theta (n^3)$ time for optimization via dynamic programming.     

Column Subset Selection Problem is UG-hard

We address two problems related to selecting an optimal subset of columns from a matrix. In one of these problems, we are given a matrix A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$ and a positive integer k, and we want to select a sub-matrix C of k   columns to minimize _{‖A−ΠCA‖F}${\Vert A-{\Pi }_{C}A\Vert }_F$, where _ΠC=CC⁺${\Pi }_C=C{C}^{+}$ denotes the matrix of projection onto the space spanned by C  . In the other problem, we are given A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$, positive integers c and r, and we want to select sub-matrices C and R of c columns and r rows of A  , respectively, to minimize _{‖A−CUR‖F}${\Vert A-CUR\Vert }_F$, where U∈R^c×r$U\in {\mathbb{R}}^{c\times r}$ is the pseudo-inverse of the intersection between C and R. Although there is a plethora of algorithmic results, the complexity of these problems has not been investigated thus far. We show that these two problems are NP-hard assuming UGC.     

Cubical local partial orders on cubically subdivided spaces—Existence and construction

The geometric models of higher dimensional automata (HDA) and Dijkstra's PV-model are cubically subdivided topological spaces with a local partial order. If a cubicalization of a topological space is free of immersed cubic Möbius bands, then there are consistent choices of direction in all cubes, such that any n  -cube in the cubic subdivision is dihomeomorphic to [0,1]ⁿ$[0,1{]}^n$ with the induced partial order from Rⁿ${\mathbb{R}}^n$. After subdivision once, any cubicalized space has a cubical local partial order. In particular, all triangularized spaces have a cubical local partial order. This implies in particular that the underlying geometry of an HDA may be quite complicated.