An efficient fixed-parameter algorithm for 3-Hitting Set

Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S′S with |S′|k, so that S′ contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270^k+n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(c^k+n) time algorithm with c=d−1+O(d⁻¹).     

The maximum clique problem

In this paper we present a survey of results concerning algorithms, complexity, and applications of the maximum clique problem. We discuss enumerative and exact algorithms, heuristics, and a variety of other proposed methods. An up to date bibliography on the maximum clique and related problems is also provided.     

Algorithms for the single-source uncapacitated minimum concave-cost network flow problem

We investigate algorithms, applications, and complexity issues for the single-source uncapacitated (SSU) version of the minimum concave-cost network flow problem (MCNFP). We present applications arising from production planning, and prove complexity results for both global and local search. We formally state the local search algorithm of Gallo and Sodini [5], and present alternative local search algorithms. Computational results are provided to compare the various local search algorithms proposed and the effects of initial solution techniques.     

An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k₁, k₂, is there a vertex cover taking at most k₁ vertices from one and at most k₂ vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999^{k₁ + k₂} + (k₁ + k₂)n) time. Our algorithm is efficient and practical for small values of k₁ and k₂, as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed; nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths (and hence the depth of the search tree as a whole) by a sort of bonus points.     

An extrapolation theorem for nonlinear approximation and its applications

We prove an extrapolation theorem for the nonlinear m-term approximation with respect to a system of functions satisfying very mild conditions. This theorem allows us to prove endpoint L^p-L^q estimates in nonlinear approximation. As a consequence, some known endpoint estimates can be deduced directly and some new estimates are also obtained. Finally, applications of these new estimates are given to spherical m-widths and m-term approximation of the weighted Besov classes.     

An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths

In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink s such that (i) for each vertex v≠s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v≠s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem.     

A classification of some regular p-groups and its applications

In this paper we classify regular p-groups with type invariants (e/it, 1, 1, 1) for e⩾2 and (1, 1, 1, 1, 1). As a by-product, we give a new approach to the classification of groups of order p ⁵, p⩾5 a prime.     

On the spectral properties ofM-matrices and its applications

LetA be anM-matrix andB be aZ-matrix. In this paper we reveal the spectral relationship ofA andB under some interesting conditions. Applying this result, we solve an open problem on splittings of anM-matrix and partially answer an open problem on the level diagrams forA andB. This work is supported in part by the City University of Hong Kong Research Grant 700727 and by Natural Science Foundation of Guangdong Province.     

C-wellposedness of the complete second order abstract cauchy problem and applications

In this paper, we first give a sufficient and necessary condition for to generate an exponentially bounded -semigroup and discuss its relations to the C-wellposedness of the complete second order abstract Cauchy problem ((ACP₂) for short) in some sense. Then we use these results and those in [1] to discuss the C-(exponential) wellposedness of a kind of (ACP₂) with application backgrounds, and develop the results in [2]. This project is supported by the NNSF of China, and the Youth Science and Technique Foundation of Shanxi Province, China     

On convergence theory in fuzzy topological spaces and its applications

In this paper we introduce and study new concepts of convergence and adherent points for fuzzy filters and fuzzy nets in the light of the Q-relation and the Q-neighborhood of fuzzy points due to Pu and Liu [28]. As applications of these concepts we give several new characterizations of the closure of fuzzy sets, fuzzy Hausdorff spaces, fuzzy continuous mappings and strong Q-compactness. We show that there is a relation between the convergence of fuzzy filters and the convergence of fuzzy nets similar to the one which exists between the convergence of filters and the convergence of nets in topological spaces.     

A sample path relation for the sojourn times in G/G/1−PS systems and its applications

For the single server system under processor sharing (PS) a sample path result for the sojourn times in a busy period is proved, which yields a sample path relation between the sojourn times under PS and FCFS discipline. This relation provides a corresponding one between the mean stationary sojourn times in G/G/1 under PS and FCFS. In particular, the mean stationary sojourn time in G/D/1 under PS is given in terms of the mean stationary sojourn time under FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of these results suggest an approximation of the mean stationary sojourn time in G/GI/1 under PS in terms of the mean stationary sojourn time under FCFS. Mathematics Subject Classification (MSC 2000) 60K25· 68M20· 60G17· 60G10 This work was supported by a grant from the Siemens AG.     

An efficient Fréchet differentiable high breakdown multivariate location and dispersion estimator

A good robust functional should, if possible, be efficient at the model, smooth, and have a high breakdown point. M-estimators can be made efficient and Fréchet differentiable by choosing appropriate ψ-functions but they have a breakdown point of at most 1/(p + 1) in p dimensions. On the other hand, the local smoothness of known high breakdown functionals has not been investigated. It is known that Rousseeuw's minimum volume ellipsoid estimator is not differentiable and that S-estimators based on smooth functions force a trade-off between efficiency and breakdown point. However, by using a two-step M-estimator based on the minimum volume ellipsoid we show that it is possible to obtain a highly efficient, Fréchet differentiable estimator whilst still retaining the breakdown point. This result is extended to smooth S-estimators.     

A wide class of heavy-tailed distributions and its applications

Let F(x) be a distribution function supported on [0, ∞) with an equilibrium distribution function F _e (x). In this paper we pay special attention to the hazard rate function r _e (x) of F _e (x), which is also called the equilibrium hazard rate (E.H.R.) of F(x). By the asymptotic behavior of r _e (x) we give a criterion to identify F(x) to be heavy-tailed or light-tailed. Moreover, we introduce two subclasses of heavy-tailed distributions, i.e., ℳ and ℳ*, where ℳ contains almost all the most important heavy-tailed distributions in the literature. Some further discussions on the closure properties of ℳ and ℳ* under convolution are given, showing that both of them are ideal heavy-tailed subclasses. In the paper we also study the model of independent difference ξ = Z − θ, where Z and θ are two independent and non-negative random variables. We give intimate relationships of the tail distributions of ξ and Z, as well as relationships of tails of their corresponding equilibrium distributions. As applications, we apply the properties of class ℳ to risk theory. In the final, some miscellaneous problems and examples are laid, showing the complexity of characterizations on heavy-tailed distributions by means of r _e (x).      

Geometric structure of the joint N‐voM distribution manifold and its applications to sensor networks

In this paper, the geometric structure for normal distribution manifold, von Mises distribution manifold and their joint distribution manifold are firstly given by the metric, curvature, and divergence, respectively. Furthermore, the active detection with sensor networks is presented by a classical measurement model based on metric manifold, and the information resolution is presented for the range and angle measurements sensor networks. The preliminary analysis results introduced in this paper indicate that our approach is able to offer consistent and more comprehensive means to understand and solve sensor network problems containing sensors management and target detection, which are not easy to be handled by conventional analysis methods.     

An everywhere convergent series representation of the distribution of Hotelling's generalized T0

A new series representation of the exact distribution of Hotelling's generalized T₀² statistic is obtained. Unlike earlier work, the series representation given here is everywhere convergent. Explicit formulae are given for both the null and the non-central distributions. Earlier results by [1], 215–225), which are convergent on the interval [0, 1), are also derived quite simply from our formulae. The paper therefore provides a solution to the long standing problem of the exact distribution of the T₀² statistic in the general case.     

A simple formula for an analogue of conditional wiener integrals and its applications II

Let C[0, T] denote the space of real-valued continuous functions on the interval [0, T] with an analogue w _ϕ of Wiener measure and for a partition 0 = t ₀ < t ₁ < ... < t _n < t _n+1 = T of [0, T], let X _n : C[0, T] → ℝ ⁿ⁺¹ and X ⁿ⁺¹: C[0, T] → ℝ ⁿ⁺² be given by X _n (x) = (x(t ₀), x(t ₁), ..., x(t _n )) and X _n+1(x) = (x(t ₀), x(t ₁), ..., x(t _n+1)), respectively. In this paper, using a simple formula for the conditional w _ϕ-integral of functions on C[0, T] with the conditioning function X _n+1, we derive a simple formula for the conditional w _ϕ-integral of the functions with the conditioning function X _n . As applications of the formula with the function X _n , we evaluate the conditional w _ϕ-integral of the functions of the form F _m (x) = ∫₀ ^T (x(t)) ^m for x ∈ C[0, T] and for any positive integer m. Moreover, with the conditioning X _n , we evaluate the conditional w _ϕ-integral of the functions in a Banach algebra which is an analogue of the Cameron and Storvick’s Banach algebra . Finally, we derive the conditional analytic Feynman w _ϕ-integrals of the functions in .      

A General Version of Standard Basis and its Application to T-Ideals

A very general version of standard basis is introduced. It covers a wide range of applications using this notion. Particularly, the standard basis of T-ideal in a free associate algebra is presented and a new variant of Spechts problem (concerning PI-algebras) is formulated. A strengthening of the Spechts conjecture is proved for nonmatrix finitely generated algebras. Mathematics Subject Classifications (2000) 16R10, 16Z05.     

Passivity-based control for Hopfield neural networks using convex representation

This paper considers the problem of passivity-based controller design for Hopfield neural networks. By making use of a convex representation of nonlinearities, a feedback control scheme based on passivity and Lyapunov theory is presented. A criterion for existence of the controller is given in terms of linear matrix inequality (LMI), which can be easily solved by a convex optimization problem. An example and its numerical simulation are given to show the effectiveness of the proposed method.     

Set controllability of Markov jump switching Boolean control networks and its applications

In this article, a novel method is proposed for investigating the set controllability of Markov jump switching Boolean control networks (MJSBCNs). Specifically, the switching signal is described as a discrete-time homogeneous Markov chain. By resorting to the expectation and switching indicator function, an expectation system is constructed. Based on the expectation system, a novel verifiable condition is established for solving the set reachability of MJSBCNs. With the newly obtained results on set reachability, a necessary and sufficient condition is further derived for the set controllability of MJSBCNs. The obtained results are applied to Boolean control networks with Markov jump time delays. Examples are demonstrated to justify the theoretical results.