三维多面体网格上扩散方程的保正格式

 针对三维任意(星形)多面体网格, 本文构造了扩散方程的一种单元中心型非线性有限体积格式, 证明了该格式具有保正性. 在该格式设计中, 除引入网格中心量外, 还引入网格节点量和网格面中心量作为中间未知量, 它们将用网格中心未知量线性组合表示, 使得格式仅有网格中心未知量作为基本未知量. 在节点量计算中, 利用网格面上的调和平均点, 设计了一种适用于三维多面体网格的局部显式加权方法. 该格式适用于求解非平面的网格表面和间断扩散系数的问题. 数值例子验证了它对光滑解具有二阶精度和保正性.     

Finding Shortest Paths in a Sequence of Triangles in 3D by the Planar Unfolding

We present an efficient algorithm for finding the shortest path joining two points in a sequence of triangles in three-dimensional space using the concept of funnels associated with common edges along the sequence of triangles and the planar unfolding for each funnel. We show that the unfolded image of a funnel is a simple polygon, it thus is non-overlapping. Therefore, such funnels are determined iteratively to their associated common edges by the planar unfolding and the shortest path joining two points is determined by cusps of these funnels.     

组合优化若干经典问题新进展

组合优化是20世纪中后期发展起来的一个运筹学与计算机科学交叉学科分支, 研究具有离散结构的优化问题解的性质和求解方法. 由于不同离散问题的结构差异, 出现了各种各样的研究手段和技巧. 针对组合优化的若干经典问题, 简述了算法和复杂性理论的研究进展.     

Representations of unbounded optimization problems as integer programs

Any optimization problem in a finite structure can be represented as an integer or mixed-integer program in integral quantities.We show that, when an optimization problem on an unbounded structure has such a representation, it is very close to a linear programming problem, in the specific sense described in the following results. We also show that, if an optimization problem has such a representation, no more thann+2 equality constraints need be used, wheren is the number of variables of the problem.We obtain a necessary and sufficient condition for a functionf:SZ, withS Z ⁿ , to have a rational model in Meyer's sense, and show that Ibaraki models are a proper subset of Meyer models.This research was supported by NSF Grant No. GP-37510X1 and ONR Contract No. N00014-75-C0621, NR047-048.     

Stable multi-sets

In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets.  For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined.  The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks. Received: February 14, 2001/Revised version: September 7, 2001     

On the invariant faces associated with a cone-preserving map

For an nonnegative matrix , an isomorphism is obtained between the lattice of initial subsets (of ) for and the lattice of -invariant faces of the nonnegative orthant . Motivated by this isomorphism, we generalize some of the known combinatorial spectral results on a nonnegative matrix that are given in terms of its classes to results for a cone-preserving map on a polyhedral cone, formulated in terms of its invariant faces. In particular, we obtain the following extension of the famous Rothblum index theorem for a nonnegative matrix: If leaves invariant a polyhedral cone , then for each distinguished eigenvalue of for , there is a chain of distinct -invariant join-irreducible faces of , each containing in its relative interior a generalized eigenvector of corresponding to (referred to as semi-distinguished -invariant faces associated with ), where is the maximal order of distinguished generalized eigenvectors of corresponding to , but there is no such chain with more than members. We introduce the important new concepts of semi-distinguished -invariant faces, and of spectral pairs of faces associated with a cone-preserving map, and obtain several properties of a cone-preserving map that mostly involve these two concepts, when the underlying cone is polyhedral, perfect, or strictly convex and/or smooth, or is the cone of all real polynomials of degree not exceeding that are nonnegative on a closed interval. Plentiful illustrative examples are provided. Some open problems are posed at the end.

     

张量空间中的多面体锥

本文利用文献 [1 ]中的结果给出了张量空间中多面体锥的性质 ,指出当 K1,K2 分别为 V1,V2中的多面体锥时 ,由它们所生成的 V1 V2 中的最小真正锥也是多面体锥 ,这一条件不仅是充分的也是必要的 .并利用这一结果对多面体锥的已有结论给出了新的证明     

Normal surfaces as combinatorial slicings

We investigate slicings of combinatorial manifolds as properly embedded co-dimension 1 submanifolds. Focus is given to the case of dimension 3, where slicings are (discrete) normal surfaces. For the cases of 2-neighborly 3-manifolds as well as quadrangulated slicings, lower bounds on the number of quadrilaterals of slicings depending on its genus g are presented. These are shown to be sharp for infinitely many values of g. Furthermore, we classify slicings of combinatorial 3-manifolds which are weakly neighborly polyhedral maps.     

Proof of the Mixing Theorem for Statistical Systems in Classical Physics

In a general measure-theoretic context, it is proved that the action of a stochastic map on a pair of probability distributions can be characterized by the criterion of decreasing mixing distance.     

Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results

We present anO(p · n) algorithm for the problem of finding disjoint simple paths of minimum total length betweenp given pairs of terminals on oriented partial 2-trees withn nodes and positive or negative arc lengths. The algorithm is inO(n) if all terminals are distinct nodes. We characterize the convex hull of the feasible solution set for the casep=2.We gratefully acknowledge the referee's many helpful suggestions to improve the presentation of this paper.