带核元的带拒绝装箱问题

讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.     

带核的装箱问题

本文研究带核的装箱问题,提出了一个近似算法──ＲＦＦＤ算法,给出了界的估计：对任何实例Ｌ,均有ＲＦＦＤ（Ｌ）≤２／３ＯＰＴ（Ｌ）＋３／４．     

带核的装箱问题

本文研究带核的装箱问题，提出了一个近似算法──RFFD算法，给出了界的估计：对任何实的L，均有RFFD     

最大并行流问题

研究了Fleischer.L给出的求解最大并行流问题的一个近似算法,其求出的目标函数值为λ≥(1-ε)3OPT.对其算法进行了改进,给出了λ≥1/(1 3ε)OPT的最大并行流全多项式近似算法.最后给出数值例子,验证了算法的有效性.     

环上的最大最小路划分问题

证明了环上的两个最大最小路划分问题是属于P类的,并且给出了两个强多项式时间算法.     

一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP—hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP—hard问题，并可十分容易地推广到多维欧氏空间．     

工件具有累积效应的两台同类机排序问题

研究了具有累积效应的两台同类机排序问题,目标是极小化机器总载重.半积函数在组合优化通常用于算法设计与分析.对该文中涉及的问题,用该函数设计了一个γ-完全多项式近似方案,并进行了算法分析.     

环网络中的呼叫接纳控制

呼叫接纳控制是通讯网络设计与运营中的一个重要优化问题. 环网络中,这一问题的目标是对于给定的具有边容量的环网络和任意利润的呼叫的集合,确定最大利润的呼叫子集并为其中每一个呼叫安排路径,使得任一边容量不被违反. 对于无向和有向环网络呼叫接纳控制问题, 均给出了多项式时间近似方案.     

一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割;(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP,Steiner树,K-median三个著名NP-hard问题的多项式近似方案．经验表明,该技术适用于欧氏平面上对“距离和”优化的NP-hard问题,并可十分容易地推广到多维欧氏空间．