A new variance-based global sensitivity analysis technique

A new set of variance-based sensitivity indices, called W$W$-indices, is proposed. Similar to the Sobol’s indices, both main and total effect indices are defined. The W$W$-main effect indices measure the average reduction of model output variance when the ranges of a set of inputs are reduced, and the total effect indices quantify the average residual variance when the ranges of the remaining inputs are reduced. Geometrical interpretations show that the W$W$-indices gather the full information of the variance ratio function, whereas, Sobol’s indices only reflect the marginal information. Then the double-loop-repeated-set Monte Carlo (MC) (denoted as DLRS MC) procedure, the double-loop-single-set MC (denoted as DLSS MC) procedure and the model emulation procedure are introduced for estimating the W$W$-indices. It is shown that the DLRS MC procedure is suitable for computing all the W$W$-indices despite its highly computational cost. The DLSS MC procedure is computationally efficient, however, it is only applicable for computing low order indices. The model emulation is able to estimate all the W$W$-indices with low computational cost as long as the model behavior is correctly captured by the emulator. The Ishigami function, a modified Sobol’s function and two engineering models are utilized for comparing the W$W$- and Sobol’s indices and verifying the efficiency and convergence of the three numerical methods. Results show that, for even an additive model, the W$W$-total effect index of one input may be significantly larger than its W$W$-main effect index. This indicates that there may exist interaction effects among the inputs of an additive model when their distribution ranges are reduced.     

MinT—Architecture and applications of the (t, m, s)-net and OOA database

Many different constructions for (t,m,s)$(t\text{,}m\text{,}s)$-nets and (t,s)$(t\text{,}s)$-sequences are known today. Propagation rules as well as connections to other mathematical objects make it difficult to determine the best net available in a given setting.     

The complexity of the zero-sum 3-flows

A zero-sum k-flow for a graph G   is a vector in the null-space of the 0,1$0,1$-incidence matrix of G   such that its entries belong to {±1,?,±(k−1)}$\{\pm 1,?,\pm (k-1)\}$. Akbari et al. (2009) [5] conjectured that if G is a graph with a zero-sum flow, then G   admits a zero-sum 6-flow. (2,3)$(2,3)$-semiregular graphs are an important family in studying zero-sum flows. Akbari et al. (2009) [5] proved that if Zero-Sum Conjecture is true for any (2,3)$(2,3)$-semiregular graph, then it is true for any graph. In this paper, we show that there is a polynomial time algorithm to determine whether a given (2,3)$(2,3)$-graph G   has a zero-sum 3-flow. In fact, we show that, there is a polynomial time algorithm to determine whether a given (2,4)$(2,4)$-graph G with n   vertices has a zero-sum 3-flow, where the number of vertices of degree four is O(log?n)$O(\log ?n)$. Furthermore, we show that it is NP-complete to determine whether a given (3,4)$(3,4)$-semiregular graph has a zero-sum 3-flow.     

Finite derivation type for Rees matrix semigroups

This paper introduces the topological finiteness condition finite derivation type   (FDT) on the class of semigroups. This notion is naturally extended from the monoid case. With this new concept we are able to prove that if a Rees matrix semigroup M[S;I,J;P]$M[S;I,J;P]$ has FDT then the semigroup S$S$ also has FDT. Given a monoid S$S$ and a finitely presented Rees matrix semigroup M[S;I,J;P]$M[S;I,J;P]$ we prove that if the ideal of S$S$ generated by the entries of P$P$ has FDT, then so does M[S;I,J;P]$M[S;I,J;P]$. In particular, we show that, for a finitely presented completely simple semigroup M$M$, the Rees matrix semigroup M=M[S;I,J;P]$M=M[S;I,J;P]$ has FDT if and only if the group S$S$ has FDT.     

On miniaturized problems in parameterized complexity theory

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t]$\mathrm{W}[t]$ lies in W[t]$\mathrm{W}[t]$, too. In particular, the miniaturization of the dominating set problem is in W[2]$\mathrm{W}[2]$. Furthermore, we investigate the relation between f(k)·n^o(k)$f(k)·n^{\mathrm{o}(k)}$ time and subexponential time algorithms for the dominating set problem and for the clique problem.     

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$.     

Chordless paths through three vertices

Consider the following problem, which we call “Chordless path through three vertices” or CP3V, for short: Given a simple undirected graph G=(V,E)$G=(V,E)$, a positive integer k, and three distinct vertices s, t  , and v∈V$v\in V$, is there a chordless path of length at most k from s   via v$v$ to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of CP3V by proving it W[1]$W[1]$-complete with respect to its natural parameter k  . Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless (s,t)$(s,t)$-path in a digraph is also W[1]$W[1]$-complete with respect to the length of the path.     

A concurrent lambda calculus with futures

We introduce a new lambda calculus with futures, λ(fut)$\lambda (\mathsf{fut})$, that models the operational semantics of concurrent statically typed functional programming languages with mixed eager and lazy threads such as Alice ML, a concurrent extension of Standard ML. λ(fut)$\lambda (\mathsf{fut})$ is a minimalist extension of the call-by-value λ$\lambda$-calculus that is sufficiently expressive to define and combine a variety of standard concurrency abstractions, such as channels, semaphores, and ports. Despite its minimality, the basic machinery of λ(fut)$\lambda (\mathsf{fut})$ is sufficiently powerful to support explicit recursion and call-by-need evaluation.     

Fast algorithms for some dominating induced matching problems

We describe O(n)$O(n)$ time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n)$O(n)$ bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m)$O(n+m)$ time algorithms we show that they can be reduced to O(n)$O(n)$ time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n²)$O(n^2)$ to O(n)$O(n)$, while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph.     

Set-theoretic generators of rational space curves

We show how to calculate three low degree set-theoretic generators (i.e., algebraic surfaces) for all rational space curves of low degree (degree ≤6$\le 6$) as well as for all higher degree rational space curves where at least one element of their μ$\mu$-basis has degree 1 from a μ$\mu$-basis of the parametrization. In addition to having low degree, at least two of these surface generators are always ruled surfaces. Whenever possible we also show how to compute two set-theoretic complete intersection generators for these rational space curves from a μ$\mu$-basis of their parametrization.     

A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

Consider a probabilistic graph G   in which the edges of E(G)$E(G)$ are perfectly reliable, but the vertices of V(G)$V(G)$ may fail with some known probabilities. Given a subset K   of V(G)$V(G)$, the K-terminal residual reliability of G is the probability that all operational vertices in K are connected to each other. This problem can be considered to be a generalization of two well-known reliability problems – the K-terminal reliability problem and the residual connectedness reliability problem.     

Multicriteria 0-1 knapsack problems with k-min objectives

This paper deals with the multicriteria 0-1 knapsack problem (KP) with k$k$-min objectives (MkMIN-KP) in which the first objective is of classical sum type and the remaining objectives are k$k$-min objective functions. The k$k$-min objectives are ordinal objectives, aiming at the maximization of the k$k$ th smallest objective coefficient in any feasible knapsack solution with at least k$k$ items in the knapsack. We develop efficient algorithms for the determination of the complete nondominated set of MkMIN-KP.     

Algorithms for a class of infinite permutation groups

Motivated by the famous 3n+1$3n+1$ conjecture, we call a mapping from Z$\mathbb{Z}$ to Z$\mathbb{Z}$residue-class-wise affine   if there is a positive integer m$m$ such that it is affine on residue classes (mod m$m$). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings.     

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.     

On Hoffman's celebrated cycling LP example

We answer two questions that naturally arise while dealing with Hoffman's celebrated 50-year-old linear program to be solved by the primal simplex method, where an angle θ$\theta$ and a scaling factor ω$\omega$ are adjustable parameters. In particular, we determine what conditions have to be imposed on ω$\omega$ for classical cycling to occur with θ=2π/5$\theta =2\pi /5$, and what on θ$\theta$ with ω=±tan(θ)$\omega =\pm \tan (\theta )$. The first answer reveals that the sufficient condition widely spread over the literature is false, so fixing it turns this example into a correct example of classical cycling. Some progress towards necessary and sufficient conditions for cycling to occur in this example is also reported.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

Choosing starting values for certain Newton–Raphson iterations

We aim at finding the best possible seed values when computing a^1/p$a^{1/p}$ using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a)$f(a)$ in the interval [_amin,_amax]$[a_{\min },a_{\max }]$, by building the sequence _xn$x_n$ defined by the Newton–Raphson iteration, the natural choice consists in choosing _x0$x_0$ equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between _x0$x_0$ and f(a)$f(a)$. And yet, if we perform n$n$ iterations, what matters is to minimize the maximum possible distance between _xn$x_n$ and f(a)$f(a)$. In several examples, the value of the best starting point varies rather significantly with the number of iterations.     

(r|p)-centroid problems on networks with vertex and edge demand

This paper analyzes (r|p)-centroid$(r|p)\mathrm{-}\mathrm{centroid}$ problems on networks with vertex and edge demand under a binary choice rule. Bilevel programming models are presented for the discrete problem class. Furthermore, NP-hardness proofs for the discrete and continuous (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ problem on general networks with edge demand only are provided. Nevertheless, an efficient algorithm to determine a discrete (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ of a tree network with vertex and edge demand can be derived.