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.     

Modeling a generalized ecological–economic input–output balance with delay

A solution is obtained for a generalized static model of input–output balance with delay with allowance for pollution control, the optimal trajectory being specified by a piecewise-differentiable function over [t ₀, T], and the optimal control being described by a piecewise-continuous function over [t ₀, T]. A solution algorithm is developed and results of computational modeling are presented.     

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}.     

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.     

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.     

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.     

On Steiner minimal trees withLp distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ –x ₂¦ ^p + ¦y₁ –y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < , each Steiner point is of degree exactly three. Define the Steiner ratio _p to be inf{L _s (P)/L _m (P)¦PL _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ₁ = 2/3. Chung and Graham proved ₂ > 0.842. We prove in this paper that {} = 2/3 and (2/2)_{12 p} 3/2 for anyp.This work was supported in part by the National Science Foundation of China and the President Foundation of Academia Sinica.     

Chebyshev domain truncation is inferior to fourier domain truncation for solving problems on an infinite interval

Domain truncation is the simple strategy of solving problems ony [-, ] by using a large but finite computational interval, [– L, L] Sinceu(y) is not a periodic function, spectral methods have usually employed a basis of Chebyshev polynomials,T _n(y/L). In this note, we show that becauseu(±L) must be very, very small if domain truncation is to succeed, it is always more efficient to apply a Fourier expansion instead. Roughly speaking, it requires about 100 Chebyshev polynomials to achieve the same accuracy as 64 Fourier terms. The Fourier expansion of a rapidly decaying but nonperiodic function on a large interval is also a dramatic illustration of the care that is necessary in applying asymptotic coefficient analysis. The behavior of the Fourier coefficients in the limitn for fixed intervalL isnever relevant or significant in this application.     

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.     

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.     

Design sensitivity analysis and optimization of nonlinear dynamic response for a motorcycle driving on a half-sine bump road

This paper analyses the design sensitivity of a suspension system with material and geometric nonlinearities for a motorcycle structure. The main procedures include nonlinear structural analysis, formulation of the problem with nonlinear dynamic response, design sensitivity analysis, and optimization. The incremental finite element method is used in structural analysis. The stiffness and damping parameters of the suspension system are considered as design variables. The maximum amplitude of nonlinear transient response at the seat is taken as the objective function during the optimization simulation. A more realistic finite element model for the motorcycle structure with elasto-damping elements of different material models is presented. A comparison is made of the optimum designs with and without geometric nonlinear response and is discussed.Nomenclature A amplitude of the excitation function - a ₀,a ₁ time integration constants for the Newmark method - ^t+t C _s secant viscous damping matrix at timet+t - ^t C _T tangent viscous damping matrix at timet - C linear part of ^t C _T - D _i ⁰ initial value of thei-th design variable - D _i instanenous value of thei-th design variables - ^t+t F^(t–1) total internal force vector at the end of iteration (i–1) and timet+t - ^t+t F _(NL) ^(i–1) nonlinear part of ^t+t F^(i–1) - f frequency of the excitation function - ^t+t K _s secant stiffness matrix at timet+t - ^t K _T tangent stiffness matrix at timet - K linear part of ^t K _T - effective stiffness matrix at timet - L distance between the wheel centres - M constant mass matrix - m _T number of solution time steps - NC number of constraint equations - Q nonlinear dynamic equilibrium equation of the structural system - ^t+t R external applied load vector at timet+t - t _e active time interval for the excitation function - ^t U displacement vector of the finite element assemblage at timet - velocity of the finite element assemblage at timet - ^t Ü acceleration vector of the finite element assemblage at timet - ^t+t U ⁽ⁱ⁾ displacement vector of the finite element assemblage at the end of iterationi and timet+t - velocity vector of the finite element assemblage at the end of iterationi and timet+t - ^t+t Ü⁽ⁱ⁾ acceleration vector of the finite element assemblage at the end of iterationi and timet+t - U ⁽ⁱ⁾ vector of displacement increments from the end of iteration (i–1) to the end of iterationi at timet+t - V driving speed of motorcycle - x vector of design variable - () quantities of variation - ₀ objective function - _i i-th constraint equation     

Optimal horizons for a one-parameter family of unbiased FIR filters

In this paper, we find the optimal horizons and sampling intervals, both in the sense of the minimum mean square error (MSE), for a one-parameter family of the discrete-time unbiased finite impulse response (FIR) filters. On a horizon of N_l points in the nearest past, the FIR and the model k-state are represented with the l-degree and m-degree polynomials, respectively. The noise-free state space model is observed in the presence of zero-mean noise of an arbitrary distribution and covariance. The approach is based on the following. The FIR filter produces an unbiased estimate if lm. In order to reduce the noise, N_l needs to be increased. The model fits the increased horizon with a higher degree polynomial, m>l. Minimization of the mean square error for m>l gives the optimal horizon and sampling interval. Justification is provided for the global positioning system (GPS)-based measurements of the first state of a local crystal clock provided in the presence of uniformly distributed sawtooth noise induced by the GPS timing receiver.     

Prebuckling optimal design of orthotropic variable thickness plates for inplane loading

This paper is concerned with the optimal design of orthotropic rectangular plates for shear and compressive buckling loads. Expressions for the total potential as series summations are derived for double cosine thickness varying plates and hybrid double sine thickness varying plates. An efficient Fortran coded program for analysis of simply supported plates that utilizes the Rayleigh-Ritz method until convergence has been developed. It incorporates an optimization module that reactivates analysis as required. Four types of orthotropic plates were optimized in a one parameter optimization search. Results indicate a 33% increase in capacity for shear loading and an 89% increase in capacity for compressive loading.Notation A matrix of generalized eigenvalue problem - a vector of buckled shape amplitudes - a plate dimension inx-direction - a _mn amplitude of buckled shape of plate - B matrix of generalized eigenvalue problem - B ₁ –B ₁₆ coefficients of cube of plate thickness - B ₁ –B ₉ coefficients of square of plate thickness - b plate dimension iny-direction - CCEF parameter of the FORTRAN program - COEF parameter of the FORTRAN program - COEFFICIENTS module of the FORTRAN program - D ₁,D _x,D _y,D _xy flexural rigidities for orthotropic plate - flexural rigidities for orthotropic plate per cubic thickness - DI1-DI16 modules of the FORTRAN program - DI1A-DI16A modules of the FORTRAN program - DIO1-DIO9 modules of the FORTRAN program - DIO1A-DIO9A modules of the FORTRAN program - E Young's modulus - EIGEN module of the FORTRAN program - F total potential energy of buckled plate - F _c total potential for double-cosine shape representation - F _s total potential for hybrid shape representation - FK1-FK16 modules of the FORTRAN program - FK1A-FK16A modules of the FORTRAN program - FKS1-FKS16 modules of the FORTRAN program - FKS1A-FKS16A modules of the FORTRAN program - t _avr average thickness of nonuniform plate - t(x, y) thickness varying withx andy - t ₁,t ₂,t ₃ shape coefficients - I ₁ –I ₁₆ types of integrals - J ₁ –J ₁₆ types of integrals - K ₁ –K ₅ numerical factors - L ₁ –L ₉ types of integrals - L(t) differential operator - M ₁ –M ₉ types of integrals - m number of waves inx-direction - MAIN module of the FORTRAN program - N _xy shearing force per unit distance in middle surface of plate - NWRK parameter of the FORTRAN program - n number of waves iny-direction - N _x normal force inx-direction in middle - OPTIMIZER surface of plate - OPTIMIZER module of the FORTRAN program - p integer - POSTMAN module of the FORTRAN program - q integer - S area of plate - T work of external forces - U strain energy of bending - V volume of plate - w lateral displacement of plate - {W} vector of derivatives (–w, _xx ; –w _yy ;w _xy ) - x coordinate direction - y coordinate direction - z coordinate direction - constant of proportionality - combination of integers - numerical factor - variation - numerical factor - strain energy density - Poisson's ratio On leave from the Technion-Israel Institute of Technology, Technion City, Haifa 32000, Israel     

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.     

Admissible factorizations of Hankel operators induce well-posed linear systems

One of the basic axioms of a well-posed linear system says that the Hankel operator of the input–output map of the system factors into the product of the input map and the output map. Here we prove the converse: every factorization of the Hankel operator of a bounded causal time-invariant map from L² to L² which satisfies a certain admissibility condition induces a stable well-posed linear system. In particular, there is a one-to-one correspondence between the set of all minimal stable well-posed realizations of a given stable causal time-invariant input–output map (or equivalently, of a given H^∞ transfer function) and all minimal stable admissible factorizations of the Hankel operator of this input–output map.     

Periodic input estimation for linear periodic systems: Automotive engine applications

In this paper, we consider periodic linear systems driven by T₀-periodic signals that we desire to reconstruct. The systems under consideration are of the form , y=C(t)x, x∈Rⁿ, w∈R^m, y∈R^p, (m?p?n) where A(t), A₀(t), and C(t) are T₀-periodic matrices. The period T₀ is known. The T₀-periodic input signal w(t) is unknown but is assumed to admit a finite dimensional Fourier decomposition. Our contribution is a technique to estimate w from the measurements y. In both full state measurement and partial state measurement cases, we propose an efficient observer for the coefficients of the Fourier decomposition of w(t). The proposed techniques are particularly attractive for automotive engine applications where sampling time is short. In this situation, standard estimation techniques based on Kalman filters are often discarded (because of their relative high computational burden). Relevance of our approach is supported by two practical cases of application. Detailed convergence analysis is also provided. Under standard observability conditions, we prove asymptotic convergence when the tuning parameters are chosen sufficiently small.     

A note on Rooted Survivable Networks

The (undirected) Rooted Survivable Network Design (Rooted SND) problem is: given a complete graph on node set V with edge-costs, a root sV, and (node-)connectivity requirements , find a minimum cost subgraph G that contains r(t) internally-disjoint st-paths for all tT. For large values of k=max_tTr(t) Rooted SND is at least as hard to approximate as Directed Steiner Tree [Y. Lando, Z. Nutov, Inapproximability of survivable networks, Theoret. Comput. Sci. 410 (21–23) (2009) 2122–2125]. For Rooted SND, [J. Chuzhoy, S. Khanna, Algorithms for single-source vertex-connectivity, in: FOCS, 2008, pp. 105–114] gave recently an approximation algorithm with ratio O(k²logn). Independently, and using different techniques, we obtained at the same time a simpler primal–dual algorithm with the same ratio.     

On the asymptotic behaviour of solutions of differential equations in a banach space

The purpose of this paper is to consider the asymptotic behaviour of solutions of the initial value problemdu/dt = Au + F(t, u) u(t ₀) =u ₀ t t ₀ in a Banach spaceX with an unbounded, nonlinear operatorA. Conditions are given which guarantee that for sufficiently smallu ₀ the solutions converge to zero. The problem of asymptotic stability is also treated. In the last section there are applications to partial differential equations.