Triple positive solutions for some second-order boundary value problem on a measure chain

In this paper, we study the existence of three positive solutions for the second-order two-point boundary value problem on a measure chain,

where f:[t₁,σ(t₂)]×[0,∞)×R→[0,∞) is continuous and p:[t₁,σ(t₂)]→[0,∞) a nonnegative function that is allowed to vanish on some subintervals of [t₁,σ(t₂)] of the measure chain. The method involves applications of a new fixed-point theorem due to Bai and Ge [Z.B. Bai, W.G. Ge, Existence of three positive solutions for some second order boundary-value problems, Comput. Math. Appl. 48 (2004) 699–707]. The emphasis is put on the nonlinear term f involved with the first order delta derivative x^Δ(t).     

Improved construction for universality of determinant and permanent

Valiant [L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 249–261] proved that every polynomial of formula size e is a projection of the (e+2)×(e+2) determinant polynomial. We improve “e+2” to “e+1”, also for a definition of formula size that does not count multiplications by constants as gates. Our proof imitates the “2e+2” proof of von zur Gathen [J. von zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation 4 (1987) 137–172], but uses different invariants and a tighter set of base cases.     

Eigenvalue of fourth-order -point boundary value problem with derivatives

This paper deals with the existence of positive solutions for the fourth-order nonlinear ordinary differential equation

subject to the boundary conditions:

where ,β,γ,δ≥0 are constants such that ρ=δ+γ+βδ>0, and . By means of a fixed-point theorem due to Krasnaselskii, some new existence results of positive solutions for the above multi-point boundary value problem are obtained, which improve the main results of Graef et al. [J.R. Graef, C. Qian, B. Yang, A three-point boundary value problem for nonlinear fourth-order differential equations, J. Math. Anal. Appl. 287 (2003) 217–233]. An example is given to demonstrate the main results of this paper.     

Fast algorithm for multicast and data gathering in wireless networks

Given a wireless network G=(V,E), we consider a maximum critical energy problem [J. Park, S. Sahni, Maximum lifetime broadcasting in wireless networks, IEEE Transactions on Computers 54 (9) (2005) 1081–1090] that has an objective of increasing the chances of doing a sequence of broadcasts. We present an optimal generalized solution algorithm running in improved optimal O(|V|+|E|) time, where V stands for a set of nodes and E stands for a set of links in the network. Our approach is applicable in an omnidirectional antenna model and can be used to solve the problem of multicasting traffic so as to maximize the lifetime of the network [A. Orda, B.-A. Yassour, Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas, in: Proc. ACM MOBIHOC, 2005] and a data gathering problem [K. Kalpakis, K. Dasgupta, P. Namjoshi, Maximum lifetime data gathering and aggregation in wireless sensor networks, Computer Networks 42 (2003) 697–716; Y. Xue, Y. Cui, K. Nahrstedt, Maximizing lifetime for data aggregation in wireless sensor networks, ACM Moble Networks and Applications 10 (6) (2005) 853–864] with an improved running time.     

The two-equal-disjoint path cover problem of Matching Composition Network

Embedding of paths have attracted much attention in the parallel processing. Many-to-many communication is one of the most central issues in various interconnection networks. A graph G is globally two-equal-disjoint path coverable if for any two distinct pairs of vertices (u,v) and (w,x) of G, there exist two disjoint paths P and Q satisfied that (1) P (Q, respectively) joins u and v (w and x, respectively), (2) |P|=|Q|, and (3) V(PQ)=V(G). The Matching Composition Network (MCN) is a family of networks which two components are connected by a perfect matching. In this paper, we consider the globally two-equal-disjoint path cover property of MCN. Applying our result, the Crossed cube CQ_n, the Twisted cube TQ_n, and the Möbius cube MQ_n can all be proven to be globally two-equal-disjoint path coverable for n5.     

Incremental margin algorithm for large margin classifiers

In this contribution, we introduce a new on-line approximate maximal margin learning algorithm based on an extension of the perceptron algorithm. This extension, which we call fixed margin perceptron (FMP), finds the solution of a linearly separable learning problem given a fixed margin. It is shown that this algorithm converges in updates, where γ_f<γ^* is the fixed margin, γ^* is the optimum margin and R is the radius of the ball that circumscribes the data. The incremental margin algorithm (IMA) approximates the large margin solution by successively using FMP with increasing margin values. This incremental approach always guarantees a good solution at hands. Also, it is easy to implement and avoids quadratic programming methods. IMA was tested using several different data sets and it yields results similar to those found by an SVM.     

A radial basis collocation method for Hamilton–Jacobi–Bellman equations

In this paper we propose a semi-meshless discretization method for the approximation of viscosity solutions to a first order Hamilton–Jacobi–Bellman (HJB) equation governing a class of nonlinear optimal feedback control problems. In this method, the spatial discretization is based on a collocation scheme using the global radial basis functions (RBFs) and the time variable is discretized by a standard two-level time-stepping scheme with a splitting parameter θ. A stability analysis is performed, showing that even for the explicit scheme that θ=0, the method is stable in time. Since the time discretization is consistent, the method is also convergent in time. Numerical results, performed to verify the usefulness of the method, demonstrate that the method gives accurate approximations to both of the control and state variables.     

On absolute summability factors of infinite series

In this paper a general theorem on |A,δ|_k-summability methods has been proved. This theorem includes, as a special case, a known result in [E. Savas, Factors for |A|_k Summability of infinite series, Comput. Math. Appl. 53 (2007) 1045–1049].     

Near optimal solutions to least-squares problems with stochastic uncertainty

In this paper, we consider least-squares (LS) problems where the regression data is affected by parametric stochastic uncertainty. In this setting, we study the problem of minimizing the expected value with respect to the uncertainty of the LS residual. For general nonlinear dependence of the data on the uncertain parameters, determining an exact solution to this problem is known to be computationally prohibitive. Here, we follow a probabilistic approach, and determine a probable near optimal solution by minimizing the empirical mean of the residual. Finite sample convergence of the proposed method is assessed using statistical learning methods. In particular, we prove that if one constructs the empirical approximation of the mean using a finite number N of samples, then the minimizer of this empirical approximation is, with high probability, an ε-suboptimal solution for the original problem. Moreover, this approximate solution can be efficiently determined numerically by a standard recursive algorithm. Comparisons with gradient algorithms for stochastic optimization are also discussed in the paper and several numerical examples illustrate the proposed methodology.     

Hybrid method for a general optimal sensor scheduling problem in discrete time

In this paper, we consider a general class of optimal sensor scheduling problems in discrete time. There are N₁ sensors available for acquiring data so as to estimate the needed but unknown signal. Only N₂ out of the N₁ sensors can be turned on at any moment, while different weights can be assigned to different sensors. This problem is formulated as a discrete time deterministic optimal control problem involving both discrete and continuous valued controls. A computational method is developed for solving this discrete time deterministic optimal control problem based on a branch and bound method in conjunction with a gradient-based method. The branch and bound method is used to determine the optimal schedule of sensors, where a sequence of lower bound dynamic systems is introduced so as to provide effective lower bounds for the construction of the branching rules. Each of the branches is an optimal weight vector assignment problem and a gradient-based method is developed for solving this optimal control problem. For illustration, two numerical examples are solved.     

Hermite interpolation with simple planar PH curves by speed reparametrization

We introduce a new method of solving C¹ Hermite interpolation problems, which makes it possible to use a wider range of PH curves with potentially better shapes. By characterizing PH curves by roots of their hodographs in the complex representation, we introduce PH curves of type K(t−c)²ⁿ⁺¹+d. Next, we introduce a speed reparametrization. Finally, we show that, for C¹ Hermite data, we can use PH curves of type K(t−c)²ⁿ⁺¹+d or strongly regular PH quintics satisfying the G¹ reduction of C¹ data, and use these curves to solve the original C¹ Hermite interpolation problem.     

Corrigendum to “Exponential state estimation for recurrent neural networks with distributed delays” [Neurocomputing 71(1–3) (2007) 428–438]

In the letter [Neurocomputing 71(1–3) (2007) 428–438], there exists one minor error in computing the derivative of V₂((t)) and thus, the proof of Theorem 1 needs some improvement.     

An efficient algorithm for computing moments on a block representation of a grey-scale image

Computing lower order moments is important in image processing. Suppose the input grey image with size N×N has been compressed into the block representation where the number of blocks is K, commonly K<N² due to the compression effect. This correspondence presents an efficient algorithm for computing lower order moments on the block representation directly. Our proposed algorithm takes O(K) time which is proportional to the number of blocks. Experimental results reveal the computational advantage of our proposed algorithm. In addition, the results of this paper can be viewed as a generalization of the previous result by Spiliotis and Mertzios for computing lower order moments from the binary image domain to the grey image domain.     

Fast algorithms for finding disjoint subsequences with extremal densities

We derive fast algorithms for the following problem: given a set of n points on the real line and two parameters s and p, find s disjoint intervals of maximum total length that contain at most p of the given points. Our main contribution consists of algorithms whose time bounds improve upon a straightforward dynamic programming algorithm, in the relevant case that input size n is much bigger than parameters s and p. These results are achieved by selecting a few candidate intervals that are provably sufficient for building an optimal solution via dynamic programming. As a byproduct of this idea we improve an algorithm for a similar subsequence problem of Chen et al. [Disjoint segments with maximum density, in: International Workshop on Bioinformatics Research and Applications IWBRA 2005, (within ICCS 2005), Lecture Notes in Computer Science, vol. 3515, Springer, Berlin, pp. 845–850]. The problems are motivated by the search for significant patterns in biological data. Finally, we propose several heuristics that further reduce the time complexity in typical instances. One of them leads to an apparently open subsequence sum problem of independent interest.     

Scheduling in polling systems

We present a simple mean value analysis (MVA) framework for analyzing the effect of scheduling within queues in classical asymmetric polling systems with gated or exhaustive service. Scheduling in polling systems finds many applications in computer and communication systems. Our framework leads not only to unification but also to extension of the literature studying scheduling in polling systems. It illustrates that a large class of scheduling policies behaves similarly in the exhaustive polling model and the standard M/GI/1 model, whereas scheduling policies in the gated polling model behave very differently than in an M/GI/1.     

Uniqueness theorems on meromorphic functions sharing one value

In this paper, we study with a weighted sharing method the uniqueness problem of [fⁿ(z)]^(k) and [gⁿ(z)]^(k) sharing one value and obtain some results which extend the theorems given by M. Fang, S. Bhoosnurmath and S. Dyavanal et al.     

Compensation of the thermal influence on a high accuracy optical fibre displacement sensor

Thermal drifts are the main sources of error on measurements made with a high accuracy extrinsic optical fibre displacement sensor. We propose a theoretical model which can be used to calculate the influence of temperature permitting hence to correct the measurement. Our model is based on the analysis of the effect of the temperature on electronic and optoelectronic components of the sensor. The model has been experimentally validated at a mesoscopic range of accuracy (1σ300 nm) using a custom-made optical fibre sensor.     

Fault-tolerant and progressive transmission of images

A fault-tolerant progressive image transmission method is proposed. The advantages include the following: (1) Unlike most progressive methods, the image is divided into n parts with equal importance to avoid worrying about which part is lost or transmitted first. (2) If the image is a secret image, then the transmission can use n distinct channels (one shared result per channel), and intercepting up to r₁-1 channels by the enemy (r₁r_kn are all pre-set constants) will not reveal any secret. Meanwhile, the disconnection up to n-r_k channels will not affect the lossless recovery of the secret image.     

Causal reasoning by evaluating the complexity of conditional densities with kernel methods

We propose a method to quantify the complexity of conditional probability measures by a Hilbert space seminorm of the logarithm of its density. The concept of reproducing kernel Hilbert spaces (RKHSs) is a flexible tool to define such a seminorm by choosing an appropriate kernel. We present several examples with artificial data sets where our kernel-based complexity measure is consistent with our intuitive understanding of complexity of densities.

The intention behind the complexity measure is to provide a new approach to inferring causal directions. The idea is that the factorization of the joint probability measure P(effect,cause) into P(effect|cause)P(cause) leads typically to “simpler” and “smoother” terms than the factorization into P(cause|effect)P(effect). Since the conventional constraint-based approach of causal discovery is not able to determine the causal direction between only two variables, our inference principle can in particular be useful when combined with other existing methods.

We provide several simple examples with real-world data where the true causal directions indeed lead to simpler (conditional) densities.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].