谈谈斯坦纳树

谈谈斯坦纳树堵丁柱中国科学院应用数学研究所１０００８０）１费尔马的问题最短网络是项历史悠久的数学课题．它的历史可以追溯到费尔马．１６４０年，费尔马提出如下问题：于平面上给出Ａ，Ｂ，Ｃ三点，求一点Ｓ使距离和ＳＡ＋ＳＢ＋ＳＣ达到最小．该问题引起了许多人的...     

最小度生成树的一种近似算法

最小度生成树问题是一个NP难问题.本文给出了求最小度生成树的一种近似算法,这种算法得到的生成树的度数比最优解至多大1.     

树的补图的区间图完全化问题

一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值.     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

一类带约束min-max-min问题的区间算法

构造了求解一类带不等式约束的min-max-min问题的区间算法,其中目标函数和约束函数都是一阶连续可微函数,证明了方法的收敛性,给出了数值算例.该方法可以同时求出问题的最优值和全部全局最优解,是有效和可靠的.     

基于区间灰色区间直觉不确定语言集的工程项目风险辨识和评价

针对具有信息灰性、模糊性及语言描述性的工程项目风险问题,定义区间灰色区间直觉不确定语言集用于表达这些特征,结合多属性群决策理论和C-OWA算子,构建工程项目风险辨识和风险评价模型,以南京市纬三路过江隧道为例验证所建模型的可行性。结果表明,该模型可以利用区间灰度、区间隶属度和区间非隶属度以及不确定语言变量,更全面、更真实地表达工程项目的实际信息,得到更符合工程实际的风险辨识和评价结果,帮助项目管理者更准确地预知主要风险因素和风险状态。     

关于区间数据的分布函数估计问题

随机变量的区间观察值是指在随机试验中，我们只知道随机变量X是否落入某个可以观察的区间(TL，TR](该区间可以是来自某个已知或未知的二维分布)，但不知道随机变量X的具体观察值．这类问题不同于以往讨论过的左截断，右截断或双侧截断问题．本文将所见到的一些有关分布函数方面的研究成果作了一个简要介绍，同时也给出了作者的最新研究结果．     

区间数不等式约束不确定系统的线性规划

针对不等式约束含有区间参数的不确定优化命题。证明了现有几种区间不等式评价体系的统一性，并提出了一种μ^ 的改进准则。实例分析验证了用改进的评价准则对线性不等式约束进行处理的有效性。     

区间数据的均值估计

本文在运用无偏转换思想找到区间数据均值估计的基础上,对所找到的估计量的方差进行了研究.针对区间截断情况1和区间截断情况2,找到了估计量方差有限的条件.当截断随机变量的分布在某种程度上比被截断随机变量的分布尾部更厚时,方差有限的估计量可以取到.     

瓶颈型Hamming距离下约束最小支撑树的反问题

本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小. 把瓶颈型Hamming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法.     

Minimum Global Height支撑树及相关问题

本文研究了两个组合优化问题:minimum g1obal height支撑树和minimum aveageheight支撑树问题.利用3SAT问题的时间复杂性,本文证明了这两个问题都是NP-hard的,并分别给出了一个算法,即（mgh）-算法和（mah）-算法.在非负网络中,这两个算法的时间复杂性都为O（n3）.利用第一个问题的复杂性,本文证明了minimum height支撑树问题也是NP-hard的,从而纠正了有关文献中的一个错误结论.     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．     

Optimal Relay Location for Resource-limited Energy-efficient Wireless Communication

In the design of wireless networks, techniques for improving energy efficiency and extending network lifetime have great importance, particularly for defense and civil/rescue applications where resupplying transmitters with new batteries is not feasible. In this paper we study a method for improving the lifetime of wireless networks by minimizing the length of the longest edge in the interconnecting tree by deploying additional relay nodes at specific locations. This optimization problem, known as the Bottleneck Steiner Tree Problem (BSTP), asks to find a Steiner tree for n terminals with at most k Steiner points such that the length of the longest edge in the tree is minimized. We present a ratio- polynomial time approximation algorithm for BSTP, where is an arbitrary positive number.     

一类非光滑优化问题的区间算法

1引言 考虑下面离散minimax问题x∈X~(o)≤i≤m min max{f_i(x)},(1.1)     

度约束最小生成树的快速算法

本文对带有顶点度约束的最小生成树问题，给出了一种快速近似算法，并在微机上予以实现，经大量试算，效果良好。     

AN ENCLOSURE METHOD FOR FREE BOUNDARY PROBLEMS BASED ON A LINEAR COMPLEMENTARITY PROBLEM WITH INTERVAL DATA*

This paper presents the linear complementarity problem with interval data and emphasizes its application in including the solution of an ordinary free boundary problem. This study is based on Taylor's formula with remainder and the reformulation of linear complementarity problems as nonsmooth nonlinear systems of equations.

     

INITIAL BOUNDARY VALUE PROBLEMS FOR SEMILINEAR WAVE EQUATIONS WITH DISCONTINUOUS DATA

This paper studies the initial boundary problems for semilinear strictly hyperbolic second-order equations with discontinuous data. Under the uniform Lopatinski boundary condition, the local existence theorem of discontinuous solutions and the structure of singularities of the solutions are obtained.     

局中人具有偏好关系的区间合作对策问题

针对传统的区间合作对策存在的问题,利用中心三角模糊数定义区间数的偏好关系,建立了局中人对收益有偏好关系的区间合作对策模型.定义了有相同偏好关系的区间合作对策的λ-区间核心,讨论了λ-区间核心非空的充要条件以及该区间核心的求解方法,并证明了λ-区间核心与(1-λ)截对策的区间核心之间存在双射关系.此外,对有不同偏好关系的区间合作对策进行了探讨.最后,通过一个收益分配的算例说明了该模型的适用性与该区间核心的可行性.     

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

ＴＨＥＤＥＳＩＧＮＡＮＤＡＮＡＬＹＳＩＳＯＦＡＬＧＯＲＩＴＨＭＯＦＭＩＮＩＭＵＭＣＯＳＴＳＰＡＮＮＩＮＧＴＲＥＥ￥（徐绪松，刘大成，吴丽华）ＸｕＸｕｓｏｎｇ；ＬｉｕＤａｃｈｅｎｇ；ＷｕＬｉｈｕａ（ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＷｕｈａｎＵｎｉ...     

A BALANCED OVERSAMPLING FINITE ELEMENT METHOD FOR ELLIPTIC PROBLEMS WITH OBSERVATIONAL BOUNDARY DATA

In this paper we propose a finite element method for solving elliptic equations with observational Dirichlet boundary data which may subject to random noises. The method is based on the weak formulation of Lagrangian multiplier and requires balanced oversampling of the measurements of the boundary data to control the random noises. We show the convergence of the random finite element error in expectation and, when the noise is sub-Gaussian, in the Orlicz $\psi_2$-norm which implies the probability that the finite element error estimates are violated decays exponentially. Numerical examples are included.