线性分式多乘积规划问题的多项式时间近似算法

本文首先将一般形式的线性分式多乘积规划问题(MP),转化为特殊形式的子问题.再根据子问题提出一种求解(MP)的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.

线性分式规划问题的多项式时间近似算法

本文针对线性比式和分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.

一个超图嵌入问题的多项式时间近似算法

把定义在一个圈上的超图的每个超边映射为这个圈的一条路,每条超边的顶点均在对应的映射中,要求使圈中的任一边经过的路的最大次数最小,称此问题为超图在圈中的最小嵌入问题.将此问题归结为最近串选取问题,从而证明该问题存在多项式时间近似算法.

具有禁用区间的平行机排序时间表长问题的全多项式近似方案

近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中。传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题。对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法。研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的。在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的。给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界。

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

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

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进:提出一种新的构造方法,使应用于该算法的"补丁引理"结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.

曲面上旅行商问题的多项式时间近似方案

欧氏旅行商问题(TSP)的多项式时间近似方案(PTAS)结合了递归剖分、动态规划两种方法.相似的技术已成功用于构造多个欧氏组合优化问题的PTAS.为进一步拓展该方法的适用范围,研究曲面上的TSP.观察到球面不像平面那样可以递归正则剖分,对于可被开半球完全覆盖的小尺度球面TSP,采用的策略为将其逆球心射影到一个球内接正方形上,扰动其顶点并构造剖分网格,接着将该网格射影到球面,然后如同平面TSP的PTAS一样进行动态规划等操作.该策略被拓展到非小尺度球面TSP及更一般的一类曲面TSP.需注意的是由于球面、平面之间射影变形的不规则性,无法将球面TSP直接PTAS归约为平面TSP.

针对经典排序问题的一种新算法的近似比分析

给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配。该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法。文章在此基础上,考虑该新算法在一般问题上的近似比。文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2 ^(q)(q∈Z^(+))的近似比。紧例子表明,文中对算法的两个版本的分析都是最优的。

三台带两个服务等级的平行机排序问题算法研究

研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设计了一个近似比严格小于3/2的新算法,改进了已知结果。同时,在加工时间满足2的幂次方条件下,设计了一个新算法,并证明了该算法总能得到一个最优分配。

F2│r_j,t_j│C_(max)问题的多项式时间近似算法

针对具有到达时间和运输延迟的两机器流水车间排序问题F2│rj,tj│Cmax,证明了有运输时间约束的条件下,该问题最优排序是同顺序的,并给出了一种基于动态规划的多项式时间近似算法.

广义最大并行流算法的改进

研究了Karakostas G给出的求解最大并行流问题的一个近似算法,将其算法的参数进行了改进,给出了算法的时间复杂性不依赖于物资数k的广义最大并行流的全多项式时间近似算法,该算法只适用于广义的lossy网络。用改进后算法求出的目标函数值更接近于最优值,对该近似算法的近似性和算法的时间复杂性进行了证明。最后,用C语言编程,计算数值例子,通过对比充分验证了改进后算法的正确性和有效性。

极小化完工时间和的有界批调度问题(英文)

考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.

并行机生产与成批配送协调调度问题的近似策略

为了提高供应链体系中企业的生产效率,降低生产和运输成本,针对钢铁企业生产与产品配送特点,提出了并行机生产与成批配送协调调度问题.并行机上加工完成的订单以组批的方式配送到相应的客户,每批配送的订单需要考虑运输时间和运输费用,目标为将总完工时间与配送费用之和最小化.通过对问题的最优解进行分析,利用程序划分和动态规划方法,提出了伪多项式时间算法.结果表明,伪多项式时间算法可以成为解决该问题的全多项式时间近似策略.

凸二次规划松弛方法研究离散加工时间可控排序问题

用凸二次规划松弛方法研究离散加工时间可控的排序问题,得到界为3/2的多项式时间近似算法。

计算机算法和计算复杂性浅介

对计算复杂性的研究始于本世纪60年代末。当时离第一台电子计算机的发明已近20年。在这期间,计算机科学取得了巨大的成就,人们解决了为数众多靠人的笔难以完成的问题,但在某些问题面前却遇到了意想不到的困难。这些问题都是从理论上已证明可以用计算机解决的,解决这些问题的算法已编制出来。但是,所有这些的算法时间或存储空间的耗费都大得惊人。

弦环的实用全终端可靠度的一种计算方法(英文)

给出了弦环的实用全终端可靠度的一种计算方法 。

求解双代理带到达时间的并行机问题

研究了并行机情形下工件带释放时间的双代理调度问题及其求解方法,问题的优化目标为在代理B的工件总完工时间不超过一定值情况下最小化代理A的总完工时间。首先,证明了在单机条件下该问题即为NP-难问题;然后,采用动态规划方法分别给出了求解问题的拟多项式时间算法,并进一步给出了完全近似算法。

单台机以总完工时间为目标的批排序问题

研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3^(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.

组合最优化问题的近似算法

1980年第1期《Mathematics of Operations Research》上,刊登了一篇美国数学家 V.Klee 的文章,题目是“Combinatorial Optimization:What is the state of the art.在这篇文章中,V.Klee 指出,组合最优化今后研究的重要方向之一,是研究它们的近似算法.这样一种看法的依据是什么呢?这要从计算复杂性的理论谈起.一、计算复杂性的基本概念虽然高速度计算机的出现和广泛使电,使过去许多无法计算的问题得到了解决。

共享制造环境下的同类机排序问题

考虑了共享制造环境下的同类机排序问题.在共享制造环境中,每个工件Jj都有一个可以加工的机器集Mj,Jj可以被分别给Mj的某一台机器加工,也可以一定服务成本分配给其他剩余机器进行加工.该文的目标是最小化工件的最大完工时间加总服务成本.对于机器台数是固定常数情况,该文对经典加工模型和简单退化加工模型分别提出了基于程序划分的全多项式时间近似方案.对总服务成本不超过给定上界的限制下最小化最大完工时间问题,给出了其整数规划模型.