Efficient Simple Groups

Abstract

We prove that the simple group L ₃(5) which has order 372000 is efficient by providing an efficient presentation for it. This leaves one simple group with order less than one million, S ₄(4) which has order 979200, whose efficiency or otherwise remains to be determined.     

A Hopf Operad of Forests of Binary Trees and Related Finite-Dimensional Algebras

The structure of a Hopf operad is defined on the vector spaces spanned by forests of leaf-labeled, rooted, binary trees. An explicit formula for the coproduct and its dual product is given, using a poset on forests.     

基于LBP算子和类覆盖捕获图的人脸检测算法

针对传统人脸检测中的过分类问题,提出一种结合LBP算子与类覆盖捕获图的人脸检测算法.该算法首先用ε-LBP算子提取人脸图像纹理特征,并把对应不同ε值提取的LBP特征数据加权融合起来,形成人脸图像特征向量,然后采用类覆盖捕获图构造分类器,最终对人脸图像实现有效检测.与传统方法相比,基于随机图理论的类覆盖捕获图能够克服过分类缺陷,比其他近邻图分类器更具优势,性能也比较稳定.实验结果表明,该算法可以有效检测人脸图像,尤其对存在模糊和光照异常的人脸图像具有较高的精确度和鲁棒性.     

Efficient Pattern Matching on Graph Patterns of Bounded Treewidth

This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a connected graph with structured variables. A variable is an ordered list of vertices that can be replaced with a connected graph by a kind of hyperedge replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether a given graph pattern matches a given graph. In this paper, we show that GPMP is solvable in polynomial time if for a given graph pattern p, the lengths of all variables of p are 2 and the base graph of p is of bounded treewidth.     

Binary Image Compression via Monochromatic Pattern Substitution: Sequential and Parallel Implementations

We present a method for compressing binary images via monochromatic pattern substitution. Such method has no relevant loss of compression effectiveness if the image is partitioned into up to a thousand blocks, approximately, and each block is compressed independently. Therefore, it can be implemented on a distributed system with no interprocessor communication. In the theoretical context of unbounded parallelism, interprocessor communication is needed. Compression effectiveness has a bell-shaped behaviour which is again competitive with the sequential performance when the highest degree of parallelism is reached. Finally, the method has a speed-up if applied sequentially to an image partitioned into up to 256 blocks. It follows that such speed-up can be applied to a parallel implementation on a small scale system.     

一种新的混合流体对流竖向镜面对称对传波斑图

利用SIMPLE算法对混合流体对流的流体力学基本方程组进行了数值模拟,在混合流体分离比ψ=－0.6和矩形腔体长高比Γ=20的情况下,首次发现了一种新的竖向镜面对称对传波斑图,并初步探讨了它的动力学特性.竖向镜面对称对传波斑图的中心为驻波,随着时间的发展驻波的波长伸长.当波长增加到某个临界值时,一个滚动分裂成两个滚动,在这两个滚动之间产生一个具有180°相位差的新滚动.位于中心线上的滚动只有相位的突变及其波长的压缩或者伸长,没有对流滚动的移动,在它的两侧是向左右传播的对流滚动.驻波两次相位突变形成一个周期,驻波周期随着相对Rayleigh(瑞利)数Ra_r的增加而增加.这种对流结构存在于相对Rayleigh数Ra_r∈(3.6,4.3]的范围.当相对Rayleigh数Ra_r≤3.6时,系统出现具有缺陷的行波斑图;当Ra_r>4.3时系统过渡到行波斑图.说明竖向镜面对称对传波斑图是存在于具有缺陷的行波斑图和行波斑图之间的一种稳定的对流斑图.     

Simple Genetic Algorithm with Local Tuning: Efficient Global Optimizing Technique

Genetic algorithms are known to be efficient for global optimizing. However, they are not well suited to perform finely-tuned local searches and are prone to converge prematurely before the best solution has been found. This paper uses genetic diversity measurements to prevent premature convergence and a hybridizing genetic algorithm with simplex downhill method to speed up convergence. Three case studies show the procedure to be efficient, tough, and robust.     

O.R. in the Company Car Fleet: When Simple is Efficient

The management of a large fleet of company vehicles represents a significant administrative activity, particularly when the company is a motor vehicle manufacturer and the fleet consists of its own products. The approach taken by the Operational Research Group was to cross departmental boundaries to smooth vehicle ordering, reduce inventories of vehicles awaiting delivery and optimize resale values. The method steers between two potential pitfalls: that of ‘optimizing’ one affected department to the detriment of others, and that of developing sophisticated scheduling and forecasting algorithms which the users would not understand and therefore not trust.     

Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces

A new heuristic approach for minimizing possiblynonlinear and non-differentiable continuous spacefunctions is presented. By means of an extensivetestbed it is demonstrated that the new methodconverges faster and with more certainty than manyother acclaimed global optimization methods. The newmethod requires few control variables, is robust, easyto use, and lends itself very well to parallelcomputation.     

Forests of label-increasing trees

Label-increasing trees are fully labeled rooted trees with the restriction that the labels are in increasing order on every path from the root; the best known example is the binary case—no tree with more than two branches at the root, or internal vertices of degree greater than three—extensively examined by Foata and Schutzenberger in A Survey of Combinatorial Theory. The forests without branching restrictions are enumerated by number of trees by F_n(x) = x(x + 1)…(x + n ? 1), n >1 (F₀(x) = 1), whose equivalent: F_n(x) = Y_n(xT₁,…, xT_n), F_n(1)= T_{n + 1} = n!, is readily adapted to branching restriction.     

Efficient Genetic Algorithms Using Simple Genes Exchange Local Search Policy for the Quadratic Assignment Problem

In this paper, we describe an approach for solving the quadratic assignment problem (QAP) that is based on genetic algorithms (GA). It will be shown that a standard canonical GA (SGA), which involves genetic operators of selection, reproduction, crossover, and mutation, tends to fall short of the desired performance expected of a search algorithm. The performance deteriorates significantly as the size of the problem increases. To address this syndrome, it is common for GA-based techniques to be embedded with deterministic local search procedures. It is proposed that the local search should involve simple procedure of genome reordering that should not be too complex. More importantly, from a computational point of view, the local search should not carry with it the full cost of evaluating a chromosome after each move in the localized landscape. Results of simulation on several difficult QAP benchmarks showed the effectiveness of our approaches.     

Randomized Preprocessing of Homogeneous Linear Systems of Equations

Our randomized preprocessing enables pivoting-free and orthogonalization-free solution of homogeneous linear systems of equations. In the case of Toeplitz inputs, we decrease the estimated solution time from quadratic to nearly linear, and our tests show dramatic decrease of the CPU time as well. We prove numerical stability of our approach and extend it to solving nonsingular linear systems, inversion and generalized (Moore-Penrose) inversion of general and structured matrices by means of Newton’s iteration, approximation of a matrix by a nearby matrix that has a smaller rank or a smaller displacement rank, matrix eigen-solving, and root-finding for polynomial and secular equations and for polynomial systems of equations. Some by-products and extensions of our study can be of independent technical intersest, e.g., our extensions of the Sherman-Morrison-Woodbury formula for matrix inversion, our estimates for the condition number of randomized matrix products, and preprocessing via augmentation.     

The Asymptotic Number of Inequivalent Binary Codes and Nonisomorphic Binary Matroids

The asymptotic value as n→∞ of the number b(n) of inequivalent binary n-codes is determined. It was long known that b(n) also gives the number of nonisomorphic binary n-matroids.     

Lattices of Order-Convex Sets of Forests

We give a characterization of the class Co(F)\mathbf{Co}(\mathcal{F}) [Co(F_n)\mathrm{\mathbf{Co}}(\mathcal{F}_n), n < ω, respectively] of lattices isomorphic to convexity lattices of posets which are forests [forests of length at most n, respectively], as well as of the class Co(L)\mathbf{Co}(\mathcal{L}) of lattices isomorphic to convexity lattices of linearly ordered posets. This characterization yields that the class of finite members from Co(F)\mathbf{Co}(\mathcal{F}) [from Co(F_n)\mathbf{Co}(\mathcal{F}_n), n < ω, or from Co(L)\mathbf{Co}(\mathcal{L})] is finitely axiomatizable within the class of finite lattices.     

Binary Labeling of Graphs

Let G = (V, E) be a graph. A mapping f: E(G) → {0, l} ^m is called a mod 2 coding of G, if the induced mapping g: V(G) → {0, l} ^m , defined as \(g(v) = \sum\limits_{u \in V,uv \in E} {f(uv)}\) , assigns different vectors to the vertices of G. Note that all summations are mod 2. Let m(G) be the smallest number m for which a mod 2 coding of G is possible. Trivially, m(G) ≥ ?Log₂ |V|?. Recently, Aigner and Triesch proved that m(G) ≤ ?Log₂ |V|? + 4. In this paper, we determine m(G). More specifically, we prove that if each component of G has at least three vertices, then $$mG = \left\{ {\begin{array}{*{20}c} {k,} & {if \left| V \right| \ne 2^k - 2} \\ {k + 1,} & {else} \\ \end{array} ,} \right.$$ where k = ?Log₂ |V|?.     

Binary hyperidentities of lattices

Summary An equational identity of a given type involves two kinds of symbols: individual variables and the operation symbols. For example, the distributive identity: x (y + z) = x y + x z has three variable symbols {x, y, z} and two operation symbols {+, }. Here the variables range over all the elements of the base set while the two operation symbols are fixed. However, we shall say that an identity ishypersatisfied by a varietyV if, whenever we also allow the operation symbols to range over all polynomials of appropriate arity, the resulting identities are all satisfied byV in the usual sense. For example, the ring of integers Z; +, satisfies the above distributive law, but it does not hypersatisfy the same formal law because, e.g., the identityx + (y z) = (x + y) (x + z) is not valid. By contrast, is hypersatisfied by the variety of all distributive lattices and is thus referred to as a distributive latticehyperidentity. Thus a hyperidentity may be viewed as an equational scheme for writing a class of identities of a given type and the original identities themselves are obtained as special cases by substituting specific polynomials of appropriate arity for the operation symbols in the scheme. In this paper, we provide afinite equational scheme which is a basis for the set of all binary lattice hyperidentities of type 2, 2, .This research was supported by the NSERC operating grant # 8215     

Two Applications of Random Spanning Forests

We use random spanning forests to find, for any Markov process on a finite set of size n and any positive integer \(m \le n\), a probability law on the subsets of size m such that the mean hitting time of a random target that is drawn from this law does not depend on the starting point of the process. We use the same random forests to give probabilistic insights into the proof of an algebraic result due to Micchelli and Willoughby and used by Fill and by Miclo to study absorption times and convergence to equilibrium of reversible Markov chains. We also introduce a related coalescence and fragmentation process that leads to a number of open questions.     

The Edge Correlation of Random Forests

The conjecture was made by Kahn that a spanning forest F chosen uniformly at random from all forests of any finite graph G has the edge-negative association property. If true, the conjecture would mean that given any two edges ε₁ and ε₂ in G, the inequality \mathbbP(e₁ ? F, e₂ ? F) ￡ \mathbbP(e₁ ? F)\mathbbP(e₂ ? F){{\mathbb{P}(\varepsilon_{1} \in \mathbf{F}, \varepsilon_{2} \in \mathbf{F}) \leq \mathbb{P}(\varepsilon_{1} \in \mathbf{F})\mathbb{P}(\varepsilon_{2} \in \mathbf{F})}} would hold. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices. We derive explicit related results for random trees.