k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．     

Temporary attachment of carbohydrates to cyclopeptide templates: a new strategy for single-bead analysis of multivalent neoglycopeptides

Employing a cleavable carbohydrate–peptide linker, a new strategy for single-bead analysis of multivalent cyclic neoglycopeptides based on Edman degradation is described. Edman degradation of glycopeptides is hampered by the acid lability of the glycosidic bond and potential incompatibilities of phenylthiohydantoin (PTH) derivatives of glycosylated amino acids with PTH derivatives of the proteinogenic amino acids. To overcome this problem, carbohydrates are detached from the cyclopeptide templates before single-bead analysis, allowing for micro sequencing under routine conditions. With this strategy, application of multivalent cyclic neoglycopeptides in split-mix libraries with a subsequent screening process becomes possible for the first time.     

Conjugacy relationship between M-convex and L-convex functions in continuous variables

By extracting combinatorial structures in well-solved nonlinear combinatorial optimization problems, Murota (1996,1998) introduced the concepts of M-convexity and L-convexity to functions defined over the integer lattice. Recently, Murota–Shioura (2000, 2001) extended these concepts to polyhedral convex functions and quadratic functions in continuous variables. In this paper, we consider a further extension to more general convex functions defined over the real space, and provide a proof for the conjugacy relationship between general M-convex and L-convex functions.Mathematics Subject Classification (1991): 90C10, 90C25, 90C27, 90C35This work is supported by Grant-in-Aid of the Ministry of Education, Culture, Sports, Science and Technology of Japan     

Protein Conformation of a Lattice Model Using Tabu Search

We apply tabu search techniques to the problem of determining the optimal configuration of a chain of protein sequences on a cubic lattice. The problem under study is difficult to solve because of the large number of possible conformations and enormous amount of computations required. Tabu search is an iterative heuristic procedure which has been shown to be a remarkably effective method for solving combinatorial optimization problems. In this paper, an algorithm is designed for the cubic lattice model using tabu search. The algorithm has been tested on a chain of 27 monomers. Computational results show that our method outperforms previously reported approaches for the same model.     

Riemann Zeta函数的六阶和

利用概率论与组合数学的方法,研究了与Riemann-zeta函数ξ(k)的部分和ξ_n(k)有关的一些级数,计算出了一些重要的和式．特别的,Euler的著名结果5ξ(4)= 2ξ~2(2)能够从四阶和式直接推出．因此,通过计算全部的11个六阶和式,研究它们之间的非平凡关系,就有可能得到ξ(3)的数值．     

Characterisations of function spaces of generalised smoothness

We investigate function spaces of generalised smoothness of Besov and Triebel–Lizorkin type. Equivalent quasi-norms in terms of maximal functions and local means are given. An atomic decomposition theorem for this type of spaces is proved. Mathematics Subject Classification (2000) 46E35     

箱覆盖问题的半定松驰算法

箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果[13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。     

Asymptotic Properties of Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.