A sufficient condition for pancyclic graphs

In 2005, Rahman and Kaykobad proved that if G is a connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for each pair x, y of distinct nonadjacent vertices in G, where d(x,y) is the length of a shortest path between x and y in G, then G has a Hamiltonian path [Inform. Process. Lett. 94 (2005) 37–41]. In 2006 Li proved that if G is a 2-connected graph of order n3 such that d(x)+d(y)+d(x,y)n+2 for each pair x,y of nonadjacent vertices in G, then G is pancyclic or G=K_n/2,n/2 where n4 is an even integer [Inform. Process. Lett. 98 (2006) 159–161]. In this work we prove that if G is a 2-connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for all pairs x, y of distinct nonadjacent vertices in G, then G is pancyclic or G belongs to one of four specified families of graphs.     

Kernel nonnegative matrix factorization for spectral EEG feature extraction

Nonnegative matrix factorization (NMF) seeks a decomposition of a nonnegative matrix X0 into a product of two nonnegative factor matrices U0 and V0, such that a discrepancy between X and UV is minimized. Assuming U=XW in the decomposition (for W0), kernel NMF (KNMF) is easily derived in the framework of least squares optimization. In this paper we make use of KNMF to extract discriminative spectral features from the time–frequency representation of electroencephalogram (EEG) data, which is an important task in EEG classification. Especially when KNMF with linear kernel is used, spectral features are easily computed by a matrix multiplication, while in the standard NMF multiplicative update should be performed repeatedly with the other factor matrix fixed, or the pseudo-inverse of a matrix is required. Moreover in KNMF with linear kernel, one can easily perform feature selection or data selection, because of its sparsity nature. Experiments on two EEG datasets in brain computer interface (BCI) competition indicate the useful behavior of our proposed methods.     

Strongly Hamiltonian laceability of the even k-ary n-cube

The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N − 2 joining each pair of vertices in the same partite set, where N = |V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n  2.     

Approximate fixed point sequence for a finite family of asymptotically pseudocontractive mappings

Let E be a real Banach space and K be a nonempty, closed, convex, and bounded subset of E. Let T_i:K→K, i=1,2,…,N, be N uniformly L-Lipschitzian, uniformly asymptotically regular with sequences {ε_n}, and asymptotically pseudocontractive mappings with sequences , where {ε_n} and , i=1,2,…,N, satisfy certain mild conditions. Let a sequence {x_n} be generated from x₁K by

for all integers n1, where T_n=T_n(modN), {u_n} be a sequence in K, and {λ_n}, {θ_n} and {μ_n} are three real sequences in [0,1] satisfying appropriate conditions; then x_n−T_lx_n→0 as n→∞ for each l{1,2,…,N}.     

Quality-based supplier selection and evaluation using fuzzy data

Since fuzzy quality data are ubiquitous in the real world, under this fuzzy environment, the supplier selection and evaluation on the basis of the quality criterion is proposed in this paper. The C_pk index has been the most popular one used to evaluate the quality of supplier’s products. Using fuzzy data collected from q2 possible suppliers’ products, fuzzy estimates of q suppliers’ capability indices are obtained according to the form of resolution identity that is a well-known theorem in fuzzy sets theory. Certain optimization problems are formulated and solved to obtain α-level sets for the purpose of constructing the membership functions of fuzzy estimates of C_pki. These membership functions are sorted by using a fuzzy ranking method to choose the preferable suppliers. Finally, a numerical example is illustrated to present the possible application by incorporating fuzzy data into the quality-based supplier selection and evaluation.     

Effect of numerical integration on meshless methods

In this paper, we present the effect of numerical integration on meshless methods with shape functions that reproduce polynomials of degree k1. The meshless method was used on a second order Neumann problem and we derived an estimate for the energy norm of the error between the exact solution and the approximate solution from the meshless method under the presence of numerical integration. This estimate was obtained under the assumption that the numerical integration scheme satisfied a form of Green’s formula. We also indicated how to obtain numerical integration schemes satisfying this property.     

Representing Boolean functions as polynomials modulo composite numbers

Define the MOD _m -degree of a boolean functionF to be the smallest degree of any polynomialP, over the ring of integers modulom, such that for all 0–1 assignments , iff . We obtain the unexpected result that the MOD _m -degree of the OR ofN variables is , wherer is the number of distinct prime factors ofm. This is optimal in the case of representation by symmetric polynomials. The MOD _n function is 0 if the number of input ones is a multiple ofn and is one otherwise. We show that the MOD _m -degree of both the MOD _n and functions isN ⁽¹⁾ exactly when there is a prime dividingn but notm. The MOD _m -degree of the MOD _m function is 1; we show that the MOD _m -degree of isN ⁽¹⁾ ifm is not a power of a prime,O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD _m P classes (such as P) have this structure: MOD _m P is closed under complementation and union iffm is a prime power, and MOD _n P is a subset of MOD _m P iff all primes dividingn also dividem.     

Improved bounds on sorting by length-weighted reversals

We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(ℓ)=ℓ^α for all α0, where ℓ is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics.     

Fliess operators on Lp spaces: convergence and continuity

Fliess operators as input–output mappings are particularly useful in a number of fundamental problems concerning nonlinear realization theory. In the classical analysis of these operators, certain growth conditions on the coefficients in their series representations insure uniform and absolute convergence, provided every input is uniformly bounded by some fixed upperbound. In some emerging applications, however, it is more natural to consider other classes of inputs. In this paper, L_p function spaces are considered. In particular, it is shown that the classic growth conditions also provide sufficient conditions for convergence and continuity when the admissible inputs are from a ball in L_p[t₀,t₀+T], where T is bounded and p1. In addition, stronger global growth conditions are given that apply even for the case where T is unbounded. When the coefficients of a Fliess operator have a state space representation, it is shown that the state space model will always locally realize the corresponding input–output map on L_p[t₀,t₀+T] for sufficiently small T>0. If certain well-posedness conditions are satisfied then the state space model will globally realized the input–output mapping for unbounded T when the coefficients satisfy the global growth condition.     

Blind source separation with convolutive noise cancellation

On-line adaptive learning algorithms for cancellation of additive, convolutive noise from linear mixtures of sources with a simultaneous blind source separation are developed. Associated neural network architectures are proposed. A simple convolutive noise model is assumed, i.e. the unknown additive noise in each channel is a (FIR) filtering version of environmental noise, where some convolutive reference noise is measurable. Two approaches are considered: in the first, the noise is cancelled from the linear mixture of source signals as pre-processing, after that the source signals are separated; in the second, both source separation and additive noise cancellation are performed simultaneously. Both steps consist of adaptive learning processes. By computer simulation experiments, it was found that the first approach is applicable for a large amount of noise, whereas in the second approach, a considerable increase of the convergence speed of the separation process can be achieved. Performance and validity of the proposed approaches are demonstrated by extensive computer simulations.Nomenclature Symbol Meaning - ₄ normalised kurtosis of a signal - (t), t learning rates - m number of sources - n number of sensors - N,M order of the FIR filters - s(t) m-dimensional vector of (unknown) source signals - x(t) n-dimensional vector of mixed signals (sensors) - y(t) n-dimensional vector of separated output signals (estimated sources) - v _R(t) (unknown) primary environment noise signal - n _R(t) secondary reference noise signal - n(t) n-dimensional vector of additive noise signals - f(·),g(·) activation functions in separation rule - f _R(·) activation function in noise cancellation rule - A=[a _ij]_m×n (unknown) mixing matrix - B=[b _ij]_n×N additive noise generation matrix - H(t)=[h _ij]_n×M noise cancellation matrix - W(t)=[w _ij]_n×n global de-mixing matrix     

Monotony properties of connected visible graph searching

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most O(logn) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω(logn). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any k4, there exists a graph with connected visible search number at most k, and monotone connected visible search number >k     

To be fair or efficient or a bit of both

Introducing a new concept of (α,β)-fairness, which allows for a bounded fairness compromise, so that a source is allocated a rate neither less than 0α1, nor more than β1, times its fair share, this paper provides a framework to optimize efficiency (utilization, throughput or revenue) subject to fairness constraints in a general telecommunications network for an arbitrary fairness criterion and cost functions. We formulate a non-linear program (NLP) that finds the optimal bandwidth allocation by maximizing efficiency subject to (α,β)-fairness constraints. This leads to what we call an efficiency–fairness function, which shows the benefit in efficiency as a function of the extent to which fairness is compromised. To solve the NLP we use two algorithms. The first is a well-known branch-and-bound-based algorithm called Lipschitz Global Optimization and the second is a recently developed algorithm called Algorithm for Global Optimization Problems (AGOP).We demonstrate the applicability of the framework to a range of examples from sharing a single link to efficiency fairness issues associated with serving customers in remote communities.     

Elementary approximation algorithms for prize collecting Steiner tree problems

This paper deals with approximation algorithms for the prize collecting generalized Steiner forest problem, defined as follows. The input is an undirected graph G=(V,E), a collection T={T₁,…,T_k}, each a subset of V of size at least 2, a weight function , and a penalty function . The goal is to find a forest F that minimizes the cost of the edges of F plus the penalties paid for subsets T_i whose vertices are not all connected by F. Our main result is a -approximation for the prize collecting generalized Steiner forest problem, where n2 is the number of vertices in the graph. This obviously implies the same approximation for the special case called the prize collecting Steiner forest problem (all subsets T_i are of size 2). The approximation algorithm is obtained by applying the local ratio method, and is much simpler than the best known combinatorial algorithm for this problem.Our approach gives a -approximation for the prize collecting Steiner tree problem (all subsets T_i are of size 2 and there is some root vertex r that belongs to all of them). This latter algorithm is in fact the local ratio version of the primal-dual algorithm of Goemans and Williamson [M.X. Goemans, D.P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing 24 (2) (April 1995) 296–317]. Another special case of our main algorithm is Bar-Yehuda's local ratio -approximation for the generalized Steiner forest problem (all the penalties are infinity) [R. Bar-Yehuda, One for the price of two: a unified approach for approximating covering problems, Algorithmica 27 (2) (June 2000) 131–144]. Thus, an important contribution of this paper is in providing a natural generalization of the framework presented by Goemans and Williamson, and later by Bar-Yehuda.     

Finite gain stabilization requires analog control

A causal feedback map, taking sequences of measurements and producing sequences of controls, is denoted as finite set if, within any finite time horizon, its range is in a finite set. Bit-rate constrained or digital control are particular cases of finite-set feedback. In this paper, we show that the finite gain (FG) l_p stabilization, with 1p∞, of a discrete-time, linear and time-invariant unstable plant is impossible by finite-set feedback. In addition, we show that, under finite-set feedback, weaker (local) versions of FG l_p stability are also impossible. These facts are not obvious, since recent results have shown that input to state stabilization is viable by bit-rate constrained control. In view of such existing work, this paper leads to two conclusions: (1) even when input to state stability is attainable by finite-set feedback, small changes in the amplitude of the external excitation may cause, in relative terms, a large increase in the amplitude of the state (2) FG l_p stabilization requires logarithmic precision around zero. Since our conclusions hold with no assumption on the feedback structure, they cannot be derived from existing results. We adopt an information theoretic viewpoint, which also brings new insights into the problem of stabilization.     

Proof complexity in algebraic systems and bounded depth Frege systems with modular counting

We prove a lower bound of the formN ⁽¹⁾ on the degree of polynomials in a Nullstellensatz refutation of theCount _q polynomials over _m , whereq is a prime not dividingm. In addition, we give an explicit construction of a degreeN ⁽¹⁾ design for theCount _q principle over _m . As a corollary, using Beameet al. (1994) we obtain a lower bound of the form 2 ^N(1) for the number of formulas in a constant-depth Frege proof of the modular counting principleCount _q ^N from instances of the counting principleCount _m ^M .We discuss the polynomial calculus proof system and give a method of converting tree-like polynomial calculus derivations into low degree Nullstellensatz derivations.Further we shwo that a lower bound for proofs in a bounded depth Frege system in the language with the modular counting connectiveMOD _p follows from a lower bound on the degree of Nullstellensatz proofs with a constant number of levels of extension axioms, where the extension axioms comprise a formalization of the approximation method of Razborov (1987) and Smolensky (1987) (in fact, these two proof systems are basically equivalent).     

Polynomial enumeration of multidimensional lattices

Denoting the nonnegative (resp. signed) integers byN (resp.Z) and the real numbers byR, letK R ^m andf: R ^m R. Thenf is astoring function (resp.packing function) onK wheneverf|(Z ^m K) is an injection into (resp. bijection onto)N. Unit translations g_m of some P. Chowla [1961] polynomials are packing functions on the correspondingN ^m , and all compositions of these polynomials yield further packing functions on variousN ^r . We study this accessible family of packing functions, using standard properties ofordered trees to classify all those compositions, up to a simple equivalence, which define polynomial packing functions on eachN ^m . The numberc(m) of equivalence classes is an exponentially growing function for largem, whence the uniqueness conjecture of our prior two-dimensional work has no counterpart for largerm. We obtain the admissible degrees for composition polynomials inm variables; we describe the tre structures for all such polynomials with extremal degrees. Them-variable polynomials of least degree form a rather irregular numbera(m) of equivalence classes. Density considerations give some degree constraints on ageneral polynomial packing function whose domainK is the topological closure of a nonvoid open cone.     

Minimax FIR smoothers for deterministic continuous-time state space models

In order to design a smoother for a deterministic continuous-time state space model, a new performance criterion is proposed, which is given by a ratio of the current estimation error to the weighted energy of the deterministic disturbance applied during the recent finite horizon. Among smoothers with the deadbeat property and finite impulse response (FIR) structure, a minimax FIR smoother (MFS) is obtained to optimize the proposed performance criterion. To begin with, the functional optimization problem is formulated with respect to kernel functions of the MFS and then its solution is explicitly presented. The MFS depends only on inputs and outputs on the finite recent horizon, and is independent of any a priori state information. The MFS is first represented in an integral form for simple representation and then a differential form is introduced for efficient numerical computation. As in H_∞ IIR smoothing and H₂ IIR filtering, it is shown that the proposed MFS for a deterministic system can be interpreted as the minimum variance unbiased FIR smoother for a stochastic system.     

A combinatorial property of EOL languages

Let be an alphabet and II its nontrivial binary partition. Each word over can uniquely be decomposed in subwords (called blocks) consisting of letters of II _i only,i {1,2}. LetK ^*.K has a long block property (with respect to II), abbreviated asLB-property, if there exists a functionf:N ⁺ N ⁺ such that for everyw K and every positive integerm the number of blocks of length at mostm inw is bounded byf(m). K has a clustered block property (with respect to II), abbreviated asCB-property, if there exists a positive integern _o and a growing functiong:N ⁺ N ⁺ such that for everyw K and for every positive integerm the blocks of length at mostm can be covered by at mostn _o segments of length at mostg(m).It is proved that aCB-property always implies aLB-property but not necessarily other way around. It is proved that an EOL language has aLB-property if and only if it has aCB-property.     

Limitations of nonlinear discrete periodic control for disturbance attenuation and robust stabilization

This paper presents a performance analysis of nonlinear periodically time-varying discrete controllers acting upon a linear time-invariant discrete plant. Time-invariant controllers are distinguished from strictly periodically time-varying controllers. For a given nonlinear periodic controller, a time-invariant controller is constructed. Necessary and sufficient conditions are given under which the time-invariant controller gives strictly better control performance than the time-invariant controller from which it was obtained, for the attenuation of l_p exogenous disturbances and the robust stabilization of l_p unstructured perturbations, for all p[1,∞].