带有仲裁认证码的组合论下界

本文给出了带有仲裁认证码的组合论下界,并利用带有约束的t-设计,给出了敌方的r阶欺骗攻击成功的概率达到下界的带有仲裁认证码的组合结构。     

Blow‐up phenomena for a semilinear parabolic equation with weighted inner absorption under nonlinear boundary flux

Blow‐up phenomena for a nonlinear divergence form parabolic equation with weighted inner absorption term are investigated under nonlinear boundary flux in a bounded star‐shaped region. We assume some conditions on weight function and nonlinearities to guarantee that the solution exists globally or blows up at finite time. Moreover, by virtue of the modified differential inequality, upper and lower bounds for the blow‐up time of the solution are derived in higher dimensional spaces. Three examples are presented to illustrate applications of our results. Copyright © 2016 John Wiley & Sons, Ltd.     

Nonlinear codes with asymptotic parameters better than the Gilbert-Varshamov and the Xing Bounds

In this paper, we show that the Gilbert-Varshamov and the Xing bounds can be improved significantly around two points where these two bounds intersect by nonlinear codes from algebraic curves over finite fields.     

Matrix product codes with rosenbloom-tsfasman metric

In this article, the Rosenbloom-Tsfasman metric of matrix product codes over finite commutative rings is studied and the lower bounds for the minimal Rosenbloom-Tsfasman distances of the matrix product codes are obtained. The lower bounds of the dual codes of matrix product codes over finite commutative Frobenius rings are also given.     

非负矩阵Perron根的下界序列

非负矩阵Perron根的估计是非负矩阵理论研究的重要课题之一.如果其上下界能够表示为非负矩阵元素的易于计算的函数,那么这种估计价值更高.本文结合非负矩阵的迹分两种情况给出Perron根的下界序列,并且给出数值例子加以说明.     

Spreads, arcs, and multiple wavelength codes

We present several new families of multiple wavelength (2-dimensional) optical orthogonal codes (2D-OOCs) with ideal auto-correlation λ_a=0 (codes with at most one pulse per wavelength). We also provide a construction which yields multiple weight codes. All of our constructions produce codes that are either optimal with respect to the Johnson bound (J-optimal), or are asymptotically optimal and maximal. The constructions are based on certain pointsets in finite projective spaces of dimension k over GF(q) denoted PG(k,q).     

Singleton Bounds for Codes over Finite Rings

We introduce the Singleton bounds for codes over a finite commutative quasi-Frobenius ring.     

Blow-up analysis for a reaction–diffusion equation with weighted nonlocal inner absorptions under nonlinear boundary flux

A blow-up analysis for a nonlinear divergence form reaction–diffusion equation with weighted nonlocal inner absorption terms is considered under nonlinear boundary flux in a bounded star-shaped region. Based on the auxiliary function method and the modified differential inequality technique, we establish conditions on weight function and nonlinearities to guarantee the solution exists globally or blows up at finite time. Moreover, upper and lower bounds for the blow-up time are derived under appropriate measure in higher dimensional spaces. Three examples are presented to illustrate applications of our main results.     

Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem

In this paper, we address the 2-dimensional vector packing problem where an optimal layout for a set of items with two independent dimensions has to be found within the boundaries of a rectangle. Many practical applications in areas such as the telecommunications, transportation and production planning lead to this combinatorial problem. Here, we focus on the computation of fast lower bounds using original approaches based on the concept of dual-feasible functions.     

Polyhedra associated with identifying codes

The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size. In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for special bipartite graphs, and discuss further lines of research in order to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework.     

The New Minimum Distance Bounds of Goppa Codes and Their Decoding

A couple of new lower bounds of the minimum distance of Goppa codes is derived, using an extended field code for a Goppa code which contains the Goppa code as its subfield-subcode. Also presented are procedures for both error-only and error-and-erasure decoding for Goppa codes up to the new lower bounds, based on the Berlekamp-Massey algorithm and the Feng-Tzeng multisequence shift-register synthesis algorithms which have been used for decoding cyclic codes up to the BCH and HT(Hartmann-Tzeng) bounds.     

无容量限制设施选址问题的降阶回溯算法

无容量限制设施选址问题(uncapacitated facility location problem, UFLP)是经典组合优化中NP-Hard问题之一,在诸多领域具有广泛的应用价值。本文首先研究UFLP的数学性质,并进行了数学证明。运用这些数学性质不仅可以确定某些设施必定开设或者关闭,还可以确定某些连接边是否在服务集中,从而缩小问题的规模,加快求解速度;在此基础上设计出一个新的基于上下界的回溯算法来求解UFLP。最后,通过一个示例进一步阐述该算法的原理,结果表明该算法具有明显的可行性和有效性。     

Covering and radius-covering arrays: Constructions and classification

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.     

非负不可约矩阵Perron根新的下界序列

Estimate bounds for the Perron root of a nonnegative matrix are important in theory of nonnegative matrices. It is more practical when the bounds are expressed as an easily calculated function in elements of matrices. For the Perron root of nonnegative irreducible matrices, three sequences of lower bounds are presented by means of constructing shifted matrices, whose convergence is studied. The comparisons of the sequences with known ones are supplemented with a numerical example.     

Eigenvalue approximation from below using non-conforming finite elements

This is a survey article about using non-conforming finite elements in solving eigenvalue problems of elliptic operators,with emphasis on obtaining lower bounds. In addition,this article also contains some new materials for eigenvalue approximations of the Laplace operator,which include:1) the proof of the fact that the non-conforming Crouzeix-Raviart element approximates eigenvalues associated with smooth eigenfunctions from below;2) the proof of the fact that the non-conforming EQ rot1 element approximates eigenvalues from below on polygonal domains that can be decomposed into rectangular elements;3) the explanation of the phenomena that numerical eigenvalues λ 1,h and λ 3,h of the non-conforming Q rot1 element approximate the true eigenvalues from below for the L-shaped domain. Finally,we list several unsolved problems.     

Frames for vector spaces and affine spaces

A finite frame for a finite dimensional Hilbert space is simply a spanning sequence. We show that the linear functionals given by the dual frame vectors do not depend on the inner product, and thus it is possible to extend the frame expansion (and other elements of frame theory) to any finite spanning sequence for a vector space. The corresponding coordinate functionals generalise the dual basis (the case when the vectors are linearly independent), and are characterised by the fact that the associated Gramian matrix is an orthogonal projection. Existing generalisations of the frame expansion to Banach spaces involve an analogue of the frame bounds and frame operator.The potential applications of our results are considerable. Whenever there is a natural spanning set for a vector space, computations can be done directly with it, in an efficient and stable way. We illustrate this with a diverse range of examples, including multivariate spline spaces, generalised barycentric coordinates, and vector spaces over the rationals, such as the cyclotomic fields.     

有限域上一类等维码的下界

等维码凭借其在随机线性网络编码中的良好的差错控制得到广泛研究,对于给定维数和最小距离的等维码所含码字的最大个数目前还没有一般性结果.Tuvi Etzion和Alexander Vardy给出了一定等维码所含码字最大个数的上界和下界,首先利用对偶空间构造等维码C(n,M,2k,k),达到了此类码所含码字的下界,然后具体构造了最优等维码C(7,41,4,2).     

A problem of combinatorial designs related to authentication codes

The strong partially balanced t-designs can be used to construct authentication codes, whose probabilities P_r of successful deception in an optimum spoofing attack of order r for r = 0, 1, …, t − 1, achieve their information-theoretic lower bounds. In this paper a new family of strong partially balanced t-designs are constructed by means of rational normal curves over finite fields. Thus based on this new partially balanced t-designs a new class of authentication codes is obtained. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 417–429, 1998     

Lower bounds and stochastic optimization algorithms for uniform designs with three or four levels

New lower bounds for three- and four-level designs under the centered -discrepancy are provided. We describe necessary conditions for the existence of a uniform design meeting these lower bounds. We consider several modifications of two stochastic optimization algorithms for the problem of finding uniform or close to uniform designs under the centered -discrepancy. Besides the threshold accepting algorithm, we introduce an algorithm named balance-pursuit heuristic. This algorithm uses some combinatorial properties of inner structures required for a uniform design. Using the best specifications of these algorithms we obtain many designs whose discrepancy is lower than those obtained in previous works, as well as many new low-discrepancy designs with fairly large scale. Moreover, some of these designs meet the lower bound, i.e., are uniform designs.