Blended Hermite interpolants

In (Röschel, l997) B-spline technique was used for blending of Lagrange interpolants. In this paper we generalize this idea replacing Lagrange by Hermite interpolants. The generated subspline b(t) interpolates the Hermite input data consisting of parameter values t_i and corresponding derivatives a_i,j, j=0,…,_i−1, and is called blended Hermite interpolant (BHI). It has local control, is connected in affinely invariant way with the input and consists of integral (polynomial) segments of degree 2·k−1, where k−1max{_i}−1 denotes the degree of the B-spline basis functions used for the blending. This method automatically generates one of the possible interpolating subsplines of class C^k−1 with the advantage that no additional input data is necessary.     

A simple characterization of optimal ARMA predictors

The coefficients of the optimal steady state k-step ahead predictor for an ARMA process in general depend on k. It is shown that a simple formula completely characterizes all these coefficients.     

New results on oscillation for delay differential equations with piecewise constant argument

We introduce a new technique to obtain some new oscillation criteria for the oscillating coefficients delay differential equation with piecewise constant argument of the form x′(t) + a(t)x(t) + b(t)x({t − k}) = 0, where a(t) and b(t) are right continuous functions on [−k, ∞), k is a positive integer, and [·] denotes the greatest integer function. Our results improve and generalize the known results in the literature. Some examples are also given to demonstrate the advantage of our results.     

N-sided patches with B-spline boundaries

We present a method for constructing an n-sided patch of parametric surface, with n greater than 2. The main property of the resulting patch is that its boundary coincides with a B-spline. Thus, it can easily be connected to given B-spline surfaces with fixed continuity conditions.

The patch is built from a star-shaped input mesh that outlines a generic n-hole and a surface in a vicinity of the hole. The main advantages of the method are the following: continuity conditions of arbitrary order k can be imposed; the mesh involved can have an arbitrary number of sides and an arbitrary shape (convex or not); the simplicity of the construction process makes it an easy and flexible method; and finally, the surface near the boundary is a B-spline with piecewise uniform knot sequences and whose control points are vertices of the mesh (both knot sequences and control points are easily computed). We give implementation details for evaluating a surface point and show that the de Boor algorithm can be exploited for efficiency.     

Construction of $k$-Lipschitz Triangular Norms and Conorms From Empirical Data

This paper examines the practical construction of k -Lipschitz triangular norms and conorms from empirical data. We apply a characterization of such functions based on k-convex additive generators and translate k-convexity of piecewise linear strictly decreasing functions into a simple set of linear inequalities on their coefficients. This is the basis of a simple linear spline-fitting algorithm, which guarantees k-Lipschitz property of the resulting triangular norms and conorms.     

(h,k)-Arbiters for h-out-of-k mutual exclusion problem

h-Out-of-k mutual exclusion is a generalization of the 1-mutual exclusion problem, where there are k units of shared resources and each process requests h (1hk) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k+1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k+1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion.     

Contrast-optimal k out of n secret sharing schemes in visual cryptography

Visual cryptography and (k,n)-visual secret sharing schemes were introduced by Naor and Shamir (Advances in Cryptology — Eurocrypt 94, Springer, Berlin, 1995, pp. 1–12). A sender wishing to transmit a secret message distributes n transparencies amongst n recipients, where the transparencies contain seemingly random pictures. A (k,n)-scheme achieves the following situation: If any k recipients stack their transparencies together, then a secret message is revealed visually. On the other hand, if only k−1 recipients stack their transparencies, or analyze them by any other means, they are not able to obtain any information about the secret message. The important parameters of a scheme are its contrast, i.e., the clarity with which the message becomes visible, and the number of subpixels needed to encode one pixel of the original picture. Naor and Shamir constructed (k,k)-schemes with contrast 2^−(k−1). By an intricate result from Linial (Combinatorica 10 (1990) 349–365), they were also able to prove the optimality of these schemes. They also proved that for all fixed kn, there are (k,n)-schemes with contrast . For k=2,3,4 the contrast is approximately and . In this paper, we show that by solving a simple linear program, one is able to compute exactly the best contrast achievable in any (k,n)-scheme. The solution of the linear program also provides a representation of a corresponding scheme. For small k as well as for k=n, we are able to analytically solve the linear program. For k=2,3,4, we obtain that the optimal contrast is at least and . For k=n, we obtain a very simple proof of the optimality of Naor's and Shamir's (k,k)-schemes. In the case k=2, we are able to use a different approach via coding theory which allows us to prove an optimal tradeoff between the contrast and the number of subpixels.     

On the k-path partition of graphs

The k-path partition problem is to partition a graph into the minimum number of paths, so that none of them has length more than k, for a given positive integer k. The problem is a generalization of the Hamiltonian path problem and the problem of partitioning a graph into the minimum number of paths. The k-path partition problem remains NP-complete on the class of chordal bipartite graphs if k is part of the input, and we show that it is NP-complete on the class of comparability graphs even for k=3. On the positive side, we present a polynomial-time solution for the problem, with any k, on bipartite permutation graphs, which form a subclass of chordal bipartite graphs.     

Efficient algorithms for single- and two-layer linear placement of parallel graphs

This paper outlines an algorithm for optimum linear ordering (OLO) of a weighted parallel graph with O(n log k) worst-case time complexity, and O(n + k log(n/k) log k) expected-case time complexity, where n is the total number of nodes and k is the number of chains in the parallel graph. Next, the two-layer OLO problem is considered, where the goal is to place the nodes linearly in two routing layers minimizing the total wire length. The two-layer problem is shown to subsume the maxcut problem and a befitting heuristic algorithm is proposed. Experimental results on randomly generated samples show that the heuristic algorithm runs very fast and outputs optimum solutions in more than 90% instances.     

Enabling structural summaries for efficient update and workload adaptation

To facilitate queries over semi-structured data, various structural summaries have been proposed. Structural summaries are derived directly from data and serve as the indexes for evaluating path expressions. We introduce D(k)-index, an adaptive structural summary, for general graph-structured data. Building on previous 1-index and A(k)-index, D(k)-index is also based on the concept of bisimilarity. However, as a generalization of 1-index and A(k)-index, D(k)-index possesses the adaptive ability to adjust its structure to changes in query load. It also enables efficient update algorithms, which are crucial to real applications but have not been adequately addressed in previous literatures. Our experiments show that D(k)-index is a more effective structural summary than previous static ones as a result of its query load sensitivity. In addition, the update operations on it can be performed more efficient than on its predecessors.     

High-order implicit blending surfaces of low degree

The applicability of the so-called potential method for blending implicitly defined surfaces is extended. The extended method is able to produce blendings which are C^k-continuous, where k may be chosen arbitrarily large. The blendings consist of piecewise algebraic surfaces of low degree. Specifically, the degree is k + 1 for so-called convex corners, and 2k for an important class of non-convex corners. In general the degree is linear in k, the constant of proportionality depending on the geometry of the corner. The method is illustrated by a concrete example, where a C² blending surface of degree 4 is constructed for a certain non-convex corner.     

k-Anonymization with Minimal Loss of Information

The technique of k-anonymization allows the releasing of databases that contain personal information while ensuring some degree of individual privacy. Anonymization is usually performed by generalizing database entries. We formally study the concept of generalization, and propose three information-theoretic measures for capturing the amount of information that is lost during the anonymization process. The proposed measures are more general and more accurate than those that were proposed by Meyerson and Williams and Aggarwal et al. We study the problem of achieving k-anonymity with minimal loss of information. We prove that it is NP-hard and study polynomial approximations for the optimal solution. Our first algorithm gives an approximation guarantee of O(ln k) for two of our measures as well as for the previously studied measures. This improves the best-known O(k)-approximation in. While the previous approximation algorithms relied on the graph representation framework, our algorithm relies on a novel hypergraph representation that enables the improvement in the approximation ratio from O(k) to O(ln k). As the running time of the algorithm is O(n^2k}), we also show how to adapt the algorithm in in order to obtain an O(k)-approximation algorithm that is polynomial in both n and k.     

k元n方体的条件强匹配排除

为了度量发生故障时k元n方体对其可匹配性的保持能力,通过剖析条件故障下使得k元n方体中不存在完美匹配或几乎完美匹配所需故障集的构造,研究了条件故障下使得k元n方体不可匹配所需的最小故障数。当k ≥ 4为偶数且n ≥ 2时,得出了k元n方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画;当k ≥ 3为奇数且n ≥ 2时,给出了该k元n方体容错性参数的一个可达下界和一个可达上界。结果表明,选取k为奇数的k元n方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力;进一步地,该系统在故障数不超过2n时仍是可匹配的,要使该系统不可匹配至多需要4n-3个故障元。     

Ray representation for k-trees

k-trees have established themselves as useful data structures in pattern recognition. A fundamental operation regarding k-trees is the construction of a k-tree. We present a method to store an object as a set of rays and an algorithm to convert such a set into a k-tree. The algorithm is conceptually simple, works for any k, and builds a k-tree from the rays very fast. It produces a minimal k-tree and does not lead to intermediate storage swell.     

Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

Product from solutions for multiserver centres with concurrent classes of customers

The MultiServer centre with Concurrent Classes of Customers (MSCCC) is a service centre consisting of B parallel identical exponential servers. The customers requesting service at the MSCCC centre belong to K groups. Customers arriving at the MSCCC centre are queued in the order of their arrival. A customer from group k will go into service at the MSCCC centre provided that one or more of the B servers is free and that at most n − 1 other group k customers are in service at the MSCCC centre.

The MSCCC centre can be applied to model systems where customers simultaneously occupy two resources. The system resources are partitioned into K primary and B secondary resources. A customer of group k can access primary resource k if it already is in possession of a secondary resource and if at most n − 1 other group k customers are using primary resource k.

This paper defines the MSCCC centre and presents several examples of computer (sub)systems that can be modelled using the MSCCC centre. The MSCCC centre is shown to satisfy local balance: therefore a multiclass queuing network consisting of BCMP and MSCCC centres has a product form solution. The joint probability distribution (JPD) for a queuing network consisting of several BCMP centres and one MSCCC centre is derived. Aggregation techniques are next used to reduce the JPD to a computationally tractable form. A Mean Value Analysis algorithm is presented for calculating the closed and open chain performance measures at the MSCCC centre.     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

On space-efficient algorithms for certain NP-complete problems

Some recent results claimed the existence of a class of algorithms for certain NP-complete problems, with running time O(n^{1g k} 2^n/2) and storage requirements O(k 2^n/k), for 2 kn. In this note we show that those results do not hold, implying that an algorithm with time O(n 2^n/2) and space O(2^n/4) is still the best-known solution for such class of NP-complete problems.     

A learning scheme for a fuzzy k-NN rule

The performance of a fuzzy k-NN rule depends on the number k and a fuzzy membership-array W[l,m_R], where l and m_R denote the number of classes and the number of elements in the reference set X_R respectively. The proposed learning procedure consists in iterative finding such k and W which minimize the error rate estimate by the leaving ‘leaving one out‘ method.     

A new way of counting n

In this paper, we shall give a combinatorial proof of the following equation:

,

where m and n are positive integers, m ≤ n, and k₁, k₂, …, k_n-1 are nonnegative integers.