挠自由模的秩

本文讨论了无单位元环上挠自由模的极大无关子集,证明了左 ore 整环上挠自由模的极大无关子集都有相同的势,推广了文献的许多结果.     

模糊解释结构建模研究

本文考虑到系统元素间关系的强弱，对解释结构建模（ＩＳＭ）进行了模糊化推广，提出了模糊解释结构建模（ＦＩＳＭ），并作了较为全面地讨论。文中首先对ＦＩＳＭ中的若干基本概念给予了严格定义。继而基于模糊聚类分析，实现了λ强连通子集划分和λ区域划分。随后给出了λ级别划分的充要条件定理。     

The Number of Spanning Trees in <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>-Complements of Quasi-Threshold Graphs

In this paper we examine the classes of graphs whose K_n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of K_n, the K_n-complement of H is the graph K_n–H which is obtained from K_n by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form K_n–H admitting formulas for the number of their spanning trees.Final version received: March 18, 2004     

贪婪t－相交有限序列族

设Ｆ为有限序列族，对ａ＝（ａ１，ａ２，…，ａｎ）∈Ｆ，ａｉ为整数且０≤ａｉ≤ｓｉ（整数），记ｓ（ａ）＝｛ｊ｜１≤ｊ≤ｎ，ａｊ＞０｝，ｓ（Ｆ）＝｛ｓ（ａ）｜ａ∈Ｆ｝，及Ａ｛１，２，…，ｎ｝时Ｗ（Ａ）＝Пｉ∈Ａｓｉ．称Ｆ为贪婪ｔ－相交，如对任何ａ，ｂ∈Ｆ，至少有ｔ个ａｉ，ｂｉ＞０，且Ｗ（Ａ）≥Ｗ（（｛１，２，…，ｎ｝－Ａ）＋Ｂ）对任何Ａ∈Ｓ（Ｆ）及ＢＡ（｜Ｂ｜＝ｔ－１）成立．本文得到当ｓ１＞ｓ２＞…＞ｓｎ时的最大贪婪ｔ－相交有限序列族．     

A 3/4-Approximation Algorithm for Multiple Subset Sum

The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The problem is also a special case of the multiple knapsack problem in which all knapsacks have the same capacity and the item profits and weights coincide. Recently, polynomial time approximation schemes have been proposed for MSSP and its generalizations, see A. Caprara, H. Kellerer, and U. Pferschy (SIAM J. on Optimization, Vol. 11, pp. 308–319, 2000; Information Processing Letters, Vol. 73, pp. 111–118, 2000), C. Chekuri and S. Khanna (Proceedings of SODA 00, 2000, pp. 213–222), and H. Kellerer (Proceedings of APPROX, 1999, pp. 51–62). However, these schemes are only of theoretical interest, since they require either the solution of huge integer linear programs, or the enumeration of a huge number of possible solutions, for any reasonable value of required accuracy. In this paper, we present a polynomial-time 3/4-approximation algorithm which runs fast also in practice. Its running time is linear in the number of items and quadratic in the number of bins. The core of the algorithm is a procedure to pack triples of large items into the bins. As a byproduct of our analysis, we get the approximation guarantee for a natural greedy heuristic for the 3-Partitioning Problem.     

An algorithm for the enumeration of spanning trees

Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n ²). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.     

Banach空间中积分表示的一个反例

本文证明了存在一具有解析ＲＮＰ的Ｂａｎａｉｃｈ空间Ｘ，存在Ｘ上的Ｊｅｎｓｅｎ凸集Ｃ以及ｘ∈Ｃ，使得Ｘ上支撑在Ｃ的Ｊｅｎｓｅｎ边界点上的Ｊｅｎｓｅｎ测度均不以ｘ为重心．     

Integer sets with distinct subset sums

We give a simple, elementary new proof of a generalization of the following conjecture of Paul Erdos: the sum of the elements of a finite integer set with distinct subset sums is less than 2.

     

Compact storage schemes for formatted files by spanning trees

The use of spanning trees in the compression of data files is studied. A new upper bound for the length of the minimal spanning tree, giving the size of the compressed file, is derived. A special front compression technique is proposed for unordered files. The space demands are compared to an information theoretical lower bound of the file size.     

On cut completions of abelian lattice ordered groups

We denote by F _a the class of all abelian lattice ordered groups H such that each disjoint subset of H is finite. In this paper we prove that if G F _a, then the cut completion of G coincides with the Dedekind completion of G.