Combinatorics of Nilpotents in Symmetric Inverse Semigroups

We show how several famous combinatorial sequences appear in the context of nilpotent elements of the full symmetric inverse semigroup . These sequences appear either as cardinalities of certain nilpotent subsemigroups or as the numbers of special nilpotent elements and include the Lah numbers, the Bell numbers, the Stirling numbers of the second kind, the binomial coefficients and the Catalan numbers.AMS Subject Classification: 05A15, 20M18, 20M20, 05A19.     

On Unicycle Graphs with Maximum and Minimum Zeroth-order Genenal Randić Index

Let G be a graph and d _v denote the degree of the vertex v in G. The zeroth-order general Randić index of a graph is defined as R _α⁰(G) = ∑ _v∈V(G) d _v ^α where α is an arbitrary real number. In this paper, we obtained the lower and upper bounds for the zeroth-order general Randić index R _α⁰(G) among all unicycle graphs G of order n. We give a clear picture for R _α⁰(G) of unicycle graphs according to real number α in different intervals.     

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.     

关于k-sum-avoiding子集基数的估计

对sum-avoiding子集进行推广,对任意正整数k（k〉2）,若集合S 是A N的一个子集,且S 中任意k 个元素的和都不属于A,则S 称为集合A的k-sum-avoiding子集。估计了当｜A｜=n时, A的k-sum-avoiding子集S 的最大基数。     

Fault Tolerant Sorting—Theoretical and Empirical Analyses of the Randomized QuickMergesort Algorithm

This paper introduces a new paradigm in the design of sorting algorithms, viz., fault tolerance. Fault tolerance is an important concept in modern day computing and design workflows must accommodate this need. In general, there are a number of avenues for faults to occur and techniques to address the same; this paper focusses on only one source of faulty behavior, viz., process termination. Process termination, as a cause of faulty behavior, is important from the perspective of various applications in real-time scheduling. In order to measure the effectiveness of a fault tolerant protocol, it is necessary to define a suitable metric and analyze the performance of the protocol with respect to that metric. We measure the “unsortedness” of an array, as characterized by the number of inversion pairs that remain when the sorting algorithm (process) terminates. This paper proposes a new algorithm for sorting called the Randomized QuickMergesort (RQMS) algorithm. RQMS has a higher degree of fault tolerance than either Randomized Quicksort (RQS) or Mergesort (MS), in that fewer inversion pairs remain when it terminates. Likewise, RQMS has a lower comparison overhead than RQS and is more space-efficient than MS. Our empirical analysis, which was conducted over a wide variety of distributions, conclusively establishes that RQMS is the algorithm of choice, when fault tolerance is paramount in the application. This research was supported in part by the Air Force Office of Scientific Research under Contract FA9550-06-1-0050.     

Exploring cardinality in the era of touchscreen-based technology

This paper explores how a young child (56 m) builds an understanding of the cardinality principle through communicative, touchscreen-based activities involving talk, gesture and body engagement working via multimodal, touchscreen interface using contemporary mobile technology. Drawing upon Nemirovsky's perceptuomotor integration theoretical lens and other foundational aspects of Husserlian phenomenology, we present an in-depth case study of a preschool child developing mathematical expertise and tool fluency using an iPad application called TouchCounts to operate with cardinal numbers. Overall, this study demonstrates that the one-on-one multimodal touch, sight and auditory feedback via a touchscreen device can serve to assist in a child's development of cardinality.     

一类带限的插值小波

Ｓｈａｎｎｏｎ尺度函数具有带限性质，正交性质、取样性质，但它不在Ｌ（Ｒ）中，本文引入小波，它的尺度函数不仅具有上述性质而且在Ｌ（Ｒ）中，甚至更多。     

On Non-commuting Sets in a Finite p-group with Derived Subgroup of Prime Order

Let G be a finite group. A nonempty subset X of G is said to be noncommuting if xy≠yx for any x, y ∈ X with x≠y. If |X| ≥ |Y| for any other non-commuting set Y in G, then X is said to be a maximal non-commuting set. In this paper, we determine upper and lower bounds on the cardinality of a maximal non-commuting set in a finite p-group with derived subgroup of prime order.     

带基数约束的次模+超模(BP)函数最大化问题的流算法

本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率（$\gamma$）,我们设计了单轮读取数据的过滤-流算法,并结合次模、超模函数的全局曲率（$\kappa^{g}$）得到算法的近似比为$\min\left\{\frac{（1-\varepsilon）\gamma}{2^{\gamma}},1-\frac{\gamma}{2^{\gamma}（1-\kappa^{g}）^{2}}\right\}$。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出：次模函数和超模函数在同量级条件下,能保证在较少的时间内得到与贪婪算法相同的最优值。     

A branch and cut approach to the cardinality constrained circuit problem

The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most k edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits, and a branch-and-cut solution approach using these inequalities. Received: April 1998 / Accepted: October 2000?Published online October 26, 2001