Maximum <Emphasis Type="Italic">k</Emphasis>-Splittable <Emphasis Type="Italic">s</Emphasis>,<Emphasis Type="Italic">t</Emphasis>-Flows

Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (M k SF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M k SF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed ε>0, the computed set of alternatives contains a packing used by a (1−ε)-approximate solution. The latter result is based on the observation that (1−ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the M k SF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.     

Intuitionistic (<Emphasis Type="Italic">S</Emphasis>, <Emphasis Type="Italic">T</Emphasis>)-fuzzy hyperquasigroups

The concept of intuitionistic fuzzy subhyperquasigroups in a hyperquasigroup with respect to an s-norm and a t-norm on intuitionistic fuzzy sets is introduced and their properties of such hyperquasigroups are studied. Intuitionistic (S, T)-fuzzy relations on a hyperquasigroup G are discussed. In particular, we investigate connections hyperquasigroups with binary quasigroups.     

Continually Answering Constraint <Emphasis Type="Italic">k</Emphasis>-<Emphasis Type="Italic">NN</Emphasis> Queries in Unstructured P2P Systems

We consider the problem of efficiently computing distributed geographical k-NN queries in an unstructured peer-to-peer （P2P） system, in which each peer is managed by an individual organization and can only communicate with its logical neighboring peers. Such queries are based on local filter query statistics, and require as less communication cost as possible which makes it more difficult than the existing distributed k-NN queries. Especially, we hope to reduce candidate peers and degrade communication cost. In this paper, we propose an efficient pruning technique to minimize the number of candidate peers to be processed to answer the k-NN queries. Our approach is especially suitable for continuous k-NN queries when updating peers, including changing ranges of peers, dynamically leaving or joining peers, and updating data in a peer. In addition, simulation results show that the proposed approach outperforms the existing Minimum Bounding Rectangle （MBR）-based query approaches, especially for continuous queries.     

EP<Emphasis Type="Italic">n</Emphasis>P: An Accurate <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) Solution to the P<Emphasis Type="Italic">n</Emphasis>P Problem

We propose a non-iterative solution to the PnP problem—the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences—whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O(n ⁵) or even O(n ⁸), without being more accurate. Our method is applicable for all n≥4 and handles properly both planar and non-planar configurations. Our central idea is to express the n 3D points as a weighted sum of four virtual control points. The problem then reduces to estimating the coordinates of these control points in the camera referential, which can be done in O(n) time by expressing these coordinates as weighted sum of the eigenvectors of a 12×12 matrix and solving a small constant number of quadratic equations to pick the right weights. Furthermore, if maximal precision is required, the output of the closed-form solution can be used to initialize a Gauss-Newton scheme, which improves accuracy with negligible amount of additional time. The advantages of our method are demonstrated by thorough testing on both synthetic and real-data.     

<Emphasis Type="Italic">Mondex</Emphasis>, an electronic purse: specification and refinement checks with the <Emphasis Type="Italic">Alloy</Emphasis> model-finding method

This paper explains how the Alloy model-finding method has been used to check the specification of an electronic purse (also called smart card) system, called the Mondex case study, initially written in Z. After describing the payment protocol between two electronic purses, and presenting an overview of the Alloy model-finding method, this paper explains how technical issues about integers and conceptual issues about the object layout in Z have been tackled in Alloy, giving general methods that can be used in most case studies with Alloy. This work has also pointed out some significant bugs in the original Z specification such as reasoning bugs in the proofs, and proposes a way to solve them. J. C. P. Woodcock     

Supporting top-<Emphasis Type="Italic">k</Emphasis><Emphasis Type="Italic">join</Emphasis> queries in relational databases

Ranking queries, also known as top-k queries, produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Top-k queries are dominant in many emerging applications, e.g., multimedia retrieval by content, Web databases, data mining, middlewares, and most information retrieval applications. Current relational query processors do not handle ranking queries efficiently, especially when joins are involved. In this paper, we address supporting top-k join queries in relational query processors. We introduce a new rank-join algorithm that makes use of the individual orders of its inputs to produce join results ordered on a user-specified scoring function. The idea is to rank the join results progressively during the join operation. We introduce two physical query operators based on variants of ripple join that implement the rank-join algorithm. The operators are nonblocking and can be integrated into pipelined execution plans. We also propose an efficient heuristic designed to optimize a top-k join query by choosing the best join order. We address several practical issues and optimization heuristics to integrate the new join operators in practical query processors. We implement the new operators inside a prototype database engine based on PREDATOR. The experimental evaluation of our approach compares recent algorithms for joining ranked inputs and shows superior performance.Received: 23 December 2003, Accepted: 31 March 2004, Published online: 12 August 2004Edited by: S. AbiteboulExtended version of the paper published in the Proceedings of the 29th International Conference on Very Large Databases, VLDB 2003, Berlin, Germany, pp 754-765     

States on <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript> algebras

The aim of this paper is to introduce the notion of states on R ₀ algebras and investigate some of their properties. We prove that every R ₀ algebra possesses at least one state. Moreover, we investigate states on weak R ₀ algebras and give some examples to show that, in contrast to R ₀ algebras, there exist weak R ₀ algebras which have no states. We also derive the condition under which finite linearly ordered weak R ₀ algebras have a state. This work is supported by NSFC (No.60605017).     

<Emphasis Type="Italic">hp</Emphasis>-Version <Emphasis Type="Italic">a priori</Emphasis> Error Analysis of Interior Penalty Discontinuous Galerkin Finite Element Approximations to the Biharmonic Equation

We consider the symmetric formulation of the interior penalty discontinuous Galerkin finite element method for the numerical solution of the biharmonic equation with Dirichlet boundary conditions in a bounded polyhedral domain in . For a shape-regular family of meshes consisting of parallelepipeds, we derive hp-version a priori bounds on the global error measured in the L² norm and in broken Sobolev norms. Using these, we obtain hp-version bounds on the error in linear functionals of the solution. The bounds are optimal with respect to the mesh size h and suboptimal with respect to the degree of the piecewise polynomial approximation p. The theoretical results are confirmed by numerical experiments, and some practical applications in Poisson–Kirchhoff thin plate theory are presented.     

The <Emphasis Type="Italic">MAP</Emphasis> + <Emphasis Type="Italic">MAP/PH</Emphasis>/1/<Emphasis Type="Italic">N</Emphasis> queuing system with single and batch arrivals of customers

The single-server queuing system with finite buffer was considered. The customers may arrive one-by-one or in batches. Arrivals of single customers and their batches obey the Markov input processes. The customers from a batch taken for servicing come one at a time at the exponentially distributed time intervals. The numbers of customers in batches are distributed geometrically. The time of customer servicing has a phase-type distribution. The numbers of batches and single customers that may be simultaneously accepted by the system are controllable parameters. The joint distribution of the number of batches and the number of customers in system, loss probabilities, distribution of the time of batch sojourn, and problems of optimization were analyzed.     

Panconnectivity and edge-pancyclicity of 3-ary <Emphasis Type="Italic">N</Emphasis>-cubes

We study two topological properties of the 3-ary n-cube Q _n ³. Given two arbitrary distinct nodes x and y in Q _n ³, we prove that there exists an x–y path of every length ranging from d(x,y) to 3 ⁿ −1, where d(x,y) is the length of a shortest path between x and y. Based on this result, we prove that Q _n ³ is edge-pancyclic by showing that every edge in Q _n ³ lies on a cycle of every length ranging from 3 to 3 ⁿ .

Exact bootstrap <Emphasis Type="Italic">k</Emphasis>-nearest neighbor learners

Bootstrap aggregation, or bagging, is a method of reducing the prediction error of a statistical learner. The goal of bagging is to construct a new learner which is the expectation of the original learner with respect to the empirical distribution function. In nearly all cases, the expectation cannot be computed analytically, and bootstrap sampling is used to produce an approximation. The k-nearest neighbor learners are exceptions to this generalization, and exact bagging of many k-nearest neighbor learners is straightforward. This article presents computationally simple and fast formulae for exact bagging of k-nearest neighbor learners and extends exact bagging methods from the conventional bootstrap sampling (sampling n observations with replacement from a set of n observations) to bootstrap sub-sampling schemes (with and without replacement). In addition, a partially exact k-nearest neighbor regression learner is developed. The article also compares the prediction error associated with elementary and exact bagging k-nearest neighbor learners, and several other ensemble methods using a suite of publicly available data sets.     

Approximations in <Emphasis Type="Italic">n</Emphasis>-ary algebraic systems

Algebraic systems have many applications in the theory of sequential machines, formal languages, computer arithmetics, design of fast adders and error-correcting codes. The theory of rough sets has emerged as another major mathematical approach for managing uncertainty that arises from inexact, noisy, or incomplete information. This paper is devoted to the discussion of the relationship between algebraic systems, rough sets and fuzzy rough set models. We shall restrict ourselves to algebraic systems with one n-ary operation and we investigate some properties of approximations of n-ary semigroups. We introduce the notion of rough system in an n-ary semigroup. Fuzzy sets, a generalization of classical sets, are considered as mathematical tools to model the vagueness present in rough systems.     

A fast and adaptive method for complex-valued SAR image denoising based on <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">k</Emphasis></Subscript> norm regularization

This paper developed a fast and adaptive method for SAR complex image denoising based on l _k norm regularization, as viewed from parameters estimation. We firstly establish the relationship between denoising model and ill-posed inverse problem via convex half-quadratic regularization, and compare the difference between the estimator variance obtained from the iterative formula and biased Cramer-Rao bound, which proves the theoretic flaw of the existent methods of parameter selection. Then, the analytic expression of the model solution as the function with respect to the regularization parameter is obtained. On this basis, we study the method for selecting the regularization parameter through minimizing mean-square error of estimators and obtain the final analytic expression, which resulted in the direct calculation, high processing speed, and adaptability. Finally, the effect of regularization parameter selection on the resolution of point targets is analyzed. The experiment results of simulation and real complex-valued SAR images illustrate the validity of the proposed method. Supported by the National Natural Science Foundation of China (Grant No. 60572136), the Fundamental Research Fund of NUDT (Grant No. JC0702005)     

A Hierarchical Extension of the <Emphasis Type="Italic">D</Emphasis><Superscript>*</Superscript> Algorithm

In this paper a contribution to the practice of path planning using a new hierarchical extension of the D^* algorithm is introduced. A hierarchical graph is stratified into several abstraction levels and used to model environments for path planning. The hierarchical D^* algorithm uses a down-top strategy and a set of pre-calculated trajectories in order to improve performance. This allows optimality and specially lower computational time. It is experimentally proved how hierarchical search algorithms and on-line path planning algorithms based on topological abstractions can be combined successfully.     

<Emphasis Type="Italic">D</Emphasis>-decomposition technique state-of-the-art

It is a survey of recent extensions and new applications for the classical D-decomposition technique. We investigate the structure of the parameter space decomposition into root invariant regions for single-input single-output systems linear depending on the parameters. The D-decomposition for uncertain polynomials is considered as well as the problem of describing all stabilizing controllers of the certain structure (for instance, PID-controllers) that satisfy given H _∞-criterion. It is shown that the D-decomposition technique can be naturally linked with M-Δ framework (a general scheme for analysis of uncertain systems) and it is applicable for describing feasible sets for linear matrix inequalities. The problem of robust synthesis for linear systems can be also treated via D-decomposition technique.     

An <Emphasis Type="Italic">R</Emphasis> || <Emphasis Type="Italic">C</Emphasis><Subscript>max</Subscript> Quantum Scheduling Algorithm

Grover’s search algorithm can be applied to a wide range of problems; even problems not generally regarded as searching problems, can be reformulated to take advantage of quantum parallelism and entanglement, and lead to algorithms which show a square root speedup over their classical counterparts. In this paper, we discuss a systematic way to formulate such problems and give as an example a quantum scheduling algorithm for an R||C_max problem. R||C_max is representative for a class of scheduling problems whose goal is to find a schedule with the shortest completion time in an unrelated parallel machine environment. Given a deadline, or a range of deadlines, the algorithm presented in this paper allows us to determine if a solution to an R||C_max problem with N jobs and M machines exists, and if so, it provides the schedule. The time complexity of the quantum scheduling algorithm is while the complexity of its classical counterpart is .     

<Emphasis Type="Italic">FC</Emphasis>-normal and extended stratified logic program

This paper investigates the consistency property ofFC-normal logic program and presents an equivalent deciding condition whether a logic programP is anFC-normal program. The deciding condition describes the characterizations ofFC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification ofFC-normal program are investigated. The stratification ofFC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is anFC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finiteFC-normal program.     

Generalized fuzzy filters of <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript>-algebras

In this paper, we introduce the notions of interval valued -fuzzy filters and interval valued -fuzzy Boolean (implicative) filters in R ₀-algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters are derived. In particular, we prove that an interval valued fuzzy set F in R ₀-algebras is an interval valued -fuzzy Boolean filter if and only if it is an interval valued -fuzzy implicative filter.     

The Zariski topology on the spectrum of prime <Emphasis Type="Italic">L</Emphasis>-submodules

Let R be a commutative ring with identity and let M be an R-module. We topologize L − Spec(M), the collection of all prime L-submodules of M, analogous to that for FSpec(R), the spectrum of fuzzy prime ideals of R, and investigate the properties of this topological space. In particular, we will study the relationship between L − Spec(M) and L − Spec(R/Ann(M)) and obtain some results.     

<Emphasis Type="BoldItalic">H</Emphasis><Subscript>2</Subscript>-Control and the Separation Principle for Discrete-Time Markovian Jump Linear Systems

In this paper we consider the H₂-control problem of discrete-time Markovian jump linear systems. We assume that only an output and the jump parameters are available to the controller. It is desired to design a dynamic Markovian jump controller such that the closed-loop system is mean square stable and minimizes the H₂-norm of the system. As in the case with no jumps, we show that an optimal controller can be obtained from two sets of coupled algebraic Riccati equations, one associated with the optimal control problem when the state variable is available, and the other associated with the optimal filtering problem. This is the principle of separation for discrete-time Markovian jump linear systems. When there is only one mode of operation our results coincide with the traditional separation principle for the H₂-control of discrete-time linear systems. Date received: June 1, 2001. Date revised: October 13, 2003.