二部图上的K1,m划分问题

 考虑了二部图上的|V|-K_1,m划分问题.首先利用网络最大流与网络最小费用流算法给出了赋权二部图上该问题的1个多项式算法,然后证明了:不考虑二部图上的权重或w是一固定常数时,该算法的复杂度为O((|V|+|U|)³.最后证明了:赋权二部图上最小最大|V|-K_1,m划分问题是NP-难的.     

点赋权图上固定顶点的树划分问题

考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1k近似算法.     

限制性的带核元划分问题

考虑了限制性的带核元划分问题,即将一个整数集合划分为2个子集,使得2个核元分别在不同的子集里且每个子集至多包含k个元素,这里n/2+1≤k≤n+1,目标使2个子集中元素之和的最小者达尽可能大.对一般的k,给出了全多项式时间近似方案(FPTAS).当k=n+1时,给出了线性时间内的多项式时间近似方案(PTAS)和全多项式时间近似方案(FPTAS).     

具有距离限制的最大竞争能力选址问题

以现实生活中的最佳选址问题为背景,定义了一种新型的选址问题——具有距离限制的最大竞争能力选址问题,分析了此类问题的NP-困难性,并为之设计了一个启发式算法.     

限制的星划分问题

 研究了边赋权图上2类具有权重限制L的最小基数星划分问题-最小基数S(L)划分问题和最小基数S∑(L)划分问题的困难性.得到如下结果:①证明了一般图上最小基数S(L)划分问题的NP-完全性;②证明了一般图上最小基数S∑(L)划分问题的NP-完全性,并证明了对于任意小的正数ε,一般图上的最小基数S∑(L)划分问题不存在(3/2-ε)-近似算法,除非P=NP.     

最小最大路划分的一个启发式算法

首先证明了最小最大路划分问题是困难的,然后利用二分算法给出了特殊情形下的最优算法,最后给出了满足三角不等式的图上的一个启发式算法.     

固定顶点的树划分问题

 考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Greedy技巧,得到固定k个顶点的最小和树划分问题的最优多项式算法;②证明了固定k个顶点的最小最大树划分问题是NP-难的,并利用①的结果给出了固定k个顶点的最小最大树划分问题的一个k-近似算法.     

关于K棵支撑树的2个问题

给定一个(有向)连通图G=(V，E)，寻找k棵支撑树(边可以重复)，满足树中的边在k棵树中出现的次数不超过其容量，考虑2个问题：①k棵支撑树的费用之和尽可能小；②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法，同时应用该算法，问题②是是近似的。     

一个360度要素函数计量模型:对人力资本价值要素函数模型的修订

随着经济的发展与管理技术的不断提高,学术界逐渐认识到人力资本这一边际报酬递增的资本在企业发展中所起的巨大作用。理所当然,对其经济价值进行准确计量和估算。为了进一步适应企业在动态经济环境中计量和估算人力资本价值的需要,在还原的要素函数模型中引入技术进步函数,建立了人力资本价值计量的要素函数模型,并进行了初步的模型修订。考虑到人力资本价值计量受各方面综合因素的影响,从360度关系的视角,对人力资本价值要素函数模型做了更进一步的修订,提出了适合于企业内部应用的模糊360度要素函数计量模型。     

最小费用排序问题

两类最小费用排序问题—费用函数满足三角不等式的最小费用排序问题和费用函数不满足三角不等式的最小费用排序问题.利用排序问题的O(nln(n))算法、图论和网络流理论分别给出了这两类问题的离线的最优多项式算法,并分别给出了这2个算法的最优性和计算复杂性分析.