An exact upper bound to the maximum number of perfect matchings in cubic pseudographs

The present paper shows that the function Φ (n)=2ⁿ+1 is an upper bound to the maximum number of distinct perfect matchings in cubic, connected pseudographs with2n vertices. Moreover examples of pseudographs are given which exactly realize such a bound. This work was carried out while the author was visiting the Department of Electrical Engineering and Computer Science of the University of California at Berkeley. It was supported in part by a grant from Consiglio Nazionale delle Ricerche, Roma, Italy.     

Simulation of an n^{+}\hbox {-}n\hbox {-}n^{+} Diode by Using Globally-Hyperbolically-Closed High-Order Moment Models

By the moment closure of the Boltzmann transport equation, the extended hydrodynamic models for electron transport have been derived in Cai et al. (J Math Phys 53:103503, 2012). With the numerical scheme developed in Li et al. (2012) recently, it has been demonstrated that the derived extended hydrodynamic models can capture the major features of the solution of kinetic equations. As the application of the models and the numerical scheme proposed therein, we in this paper carry out the numerical simulation to investigate the carrier transport in $n^{+}$ - $n$ - $n^{+}$ structures by solving the moment system derived from the Boltzmann–Poisson equations. Without any additional empirical parameters than that used in directly solving the kinetic equations, we obtain numerical results by the extended hydrodynamic models with very satisfied agreement with the solution of the kinetic equations, even in case that the length of the channel is as short as 50 nm.     

An upper bound on the number of linear relations identified from noisy data by the Frisch scheme

The Frisch scheme is one of many approaches to the identification of linear relations from noisy data. Solution of the associated matrix optimization problem leads to the identification of a maximal number of such relations. To date no general solution procedure is known. Here an upper bound on the maximal number of relations that can be identified is presented. The upper bound is derived using the theory of Schur complements in conjunction with a result for the case where only one relation can be identified. The possibility of developing a completely general solution procedure using these ideas is also briefly discussed.     

An improved upper bound on the queuenumber of the hypercube

In this note, we show that the n-dimensional hypercube Q(n) can be laid out using n−2 queues for all n?5. Our result improves the previously known result for the case n?5.     

Ring Theory-Based Evolutionary Algorithm and its application to D{0-1} KP

In this paper, we propose a new view for designing an evolutionary algorithm by using algebraic theory to solve the combinatorial optimization problem. Using the addition, multiplication and inverse operation of the direct product of rings, we first propose two evolution operators: the global exploration operator (R-GEO) and the local development operator (R-LDO). Then, by utilizing the R-GEO and R-LDO to generate individuals and applying the greedy selection strategy to generate a new population, we propose a new algorithm – the Ring Theory-Based Evolutionary Algorithm (RTEA) – for the combinatorial optimization problem. Moreover, we give a new method for solving the discounted {0-1} knapsack problem (D{0–} KP) by using the RTEA. To verify the performance of the RTEA, we use it and existing algorithms to solve four kinds of large-scale instances of the D{0-1} KP. The computational results show that the RTEA performs better than the others, and it is more suitable for solving the D{0-1} KP problem. Moreover, it indicates that using algebraic theory to design evolutionary algorithms is feasible and effective.     

An upper bound on the time complexity of iterative-deepening-A*

This paper establishes an upper bound on the time complexity of iterative-deepening-A^* (IDA^*) in terms of the number of states that are surely-expanded by A^* during a state space tree search. It is shown that given an admissible evaluation function, IDA^* surely-expands in the worst caseN(N+1)/2 states, whereN is the number of states that are surely-expanded by A^*. The conditions that give rise to the worst case performance of IDA^* on any state space tree are described. Worst case examples are also given for uniform and non-uniform state space trees.This work was supported in part by the Canadian Natural Sciences and Engineering Research Council Grant NSERC3599.     

Sports tournament scheduling to determine the required number of venues subject to the minimum timeslots under given formats

We studied a two-phase, preliminary and finals, tournament, which commonly adopted for non-professional sports. The round robin tournament in divisions is played in the preliminary phase, followed by one of the three variants, namely single elimination, double elimination, and round robin in the finals phase. The objective is to determine the required number of venues (tables or courts) subject to the least timeslots under the given format. We used a diagonal symmetric matrix to pair teams to games and to schedule games in timeslots for the round robin tournament. For the preliminary phase, we proposed a procedure to find the number of divisions and the number of teams in each division that minimize the total number of games and timeslots accordingly. For the finals phase, we determined the number of venues required in the least timeslots. We then formulated a constraint programming model based on the diagonal symmetric matrix for the round robin tournament. Finally, we provided suggestions for choosing the appropriate competition format.     

The upper bound of the optimal number of clusters in fuzzy clustering

The upper bound of the optimal number of clusters in clustering algorithm is studied in this paper. A new method is proposed to solve this issue. This method shows that the rule cmax≤n~(1/n), which is popular in current papers, is reasonable in some sense. The above conclusion is tested and analyzed by some typical examples in the literature, which demonstrates the validity of the new method.     

Branching Time Logics \mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha } with Operations Until and Since Based on Bundles of Integer Numbers, Logical Consecutions, Deciding Algorithms

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem.     

基于细菌觅食算法求解折扣{0-1}背包问题的研究

折扣{0-1}背包问题（D{0-1}KP）是新型的0-1背包问题。提出了基于细菌觅食算法（BFO）求解D{0-1}KP的方法,首先描述了D{0-1}KP的两个数学模型,然后将BFO分别与两个数学模型相结合,即细菌个体分别采用二进制向量和四进制向量的编码方法,并利用贪心策略优化初始解和修复非正常编码个体,给出了求解D{0-1}KP的FirBFO和SecBFO算法。对四类实例的计算结果表明,FirBFO和SecBFO都非常适于求解大规模的D{0-1}KP实例,能得到最优解或近似比接近1的近似解。     

A selection algorithm with a practical upper bound on expected number of comparisons

A selection algorithm to find the Irth smallest element of a elements is presented. The algorithm mainly consists of the partition procedure and an improved method to choose a partitioning element. The algorithm estimates the partitioning element from a small sample so that the icth element is contained in the smaller partition between two partitions resulting from partitioning. The partitioning element is determined by using estimation of the cumulative frequency distribution in the theory of non-parametric statistics. The expected number of comparisons is found to be n + min(k, n-k) + O(n^2/3) through experimental tests where the sample size is approximately n^2/3. The experimental results show that the performance of the algorithm is improved, compared to the two known selection algorithms, particularly when the selection index is near to the median.     

A procedure for finding an improved upper bound on the number of optimal design points

Knowing an upper bound on the number of optimal design points greatly simplifies the search for an optimal design. Carathéodory’s Theorem is commonly used to identify an upper bound. However, the upper bound from Carathéodory’s Theorem is relatively loose when there are three or more parameters in the model. In this paper, an alternative approach of finding a sharper upper bound for classical optimality criteria is proposed. Examples are given to demonstrate how to use the new approach.     

A distribution-free geometric upper bound for the probability of error of a minimum distance classifier

An upperbound to the probability of error per class in a multivariate pattern classification is derived. The bound, given by

$\text{P(E|class w}{}_{\mathrm{i}}\text{)≤}\text{N}\text{R}{}^2{}_{\mathrm{i}}$

is derived with minimal assumptions; specifically the mean vectors exist and are distinct and the covariance matrices exist and are non-singular. No other assumptions are made about the nature of the distributions of the classes. In equation (i) N is the number of features in the feature (vector) space and R_i is a measure of the “radial neighbourhood” of a class. An expression for R_i is developed. A comparison to the multivariate Gaussian hypothesis is presented.