掌上多媒体通信协议的设计与实现

随着智能移动设备的普及和多媒体技术的快速发展,掌上多媒体应运而生。该文以掌上多媒体技术在服务端和客户端的应用为场景,对通信协议的设计和实现进行深入的阐述和分析,并探讨其中涉及的通信原理和算法,给出实现掌上多媒体服务技术的核心机制和关键技术。最后,该文给出掌上多媒体通信协议的多个不同应用场景。

单台机订单排序的在线与半在线算法

考虑了一类新的单台机在线模型———订单在线和半在线排序问题 ,证明了对于单台机的半在线模型 ,有R(1,MLS)≤ 1+ r1+r.

平行机排序作业中具有不同开机时间的MF算法(英文)

安排ｎ 个独立工件在ｍ 台相同平行机上作业、使总的完工时间最少．其中工件无准备时间，但机器的开机时间不同，ＬＰＴ和ＭＬＰＴ算法分别具有３２ － １２ ｍ 和４３ 的最坏性能比．这里证明了ＭＦ算法的最坏性能比不大于９７ ．

拟阵交约束分划

给出了用求最大重量拟阵交算法来求定形拟阵交 2 分划问题的最优解的一个充分条件 .

一个关于求解k-种产品选址问题的近似算法

对于k-种产品工厂选址问题,有如下描述:存在一组客户和一组可以建立工厂的厂址。现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品。在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质。问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品。对于此类问题,优化目标是最小化建厂费用以及运输费用。论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法。

独立多处理机任务静态调度问题的近似算法

研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的2m+1近似算法和问题Pm|fix|Cmax的2 m近似算法,优于目前已有文献的最好结果.

拟阵基图的1 Hamilton 性质(英文)

研究了拟阵基图的１Ｈａｍｉｌｔｏｎ 性质，证明了基图或者是１Ｈａｍｉｌｔｏｎ 连通的，或者是一个超方体，或者与Ｋ２ ×Ｋ３ 和５ 轮Ｗ５ 中之一同构．

P_4|fix|C_(max)问题的最优规则调度算法

多处理机任务调度问题Pm|fix|Cmax(m3)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.

Harary图的最优Super-λ性质

在给定的顶点数n和边数e的所有图中,Harary图有最大的连通度[2en],因此它是一个较好的网络模型.给出了Harary图的可靠性分析,证明了它是最优Super λ图;而且精确地计算了它的限制性边连通度和i 边割集的数目mi.

一类多产品选址算法的若干进展

在对k-种产品选址问题的前期探讨中,提出了一种用于求解k-PUFLPN(即:设建厂费用为零时,k-种产品工厂选址问题)的近似算法ME,并证明了该算法的最坏性能比不大于3k/2-1,从而把性能比从2k-1提高到3k/2-1。基于前期对算法已有的分析和结论之上,进一步对该算法求解2-种产品选址模型的紧界进行了讨论。通过构造2-种产品模型的实例,给出了2是算法ME求解2-种产品选址问题的紧界这一结论。对2-种产品选址问题的整性间隙也进行了分析和讨论。

掌上多媒体技术在教学中的应用

描述掌上多媒体的软、硬件构成和主要功能,以及其应用于教学的步骤和方法。掌上多媒体继承了现有多媒体所有的功能和优点,并扩展了更多功能,能很好地改善教学效果:智能手机或平板电脑可以在教室的任何位置操作多媒体计算机;平板电脑上的书写可以实时在投影上出现,克服了反光、遮挡部分学生的缺点;实现课件现场上传。

图的子图中 (n ,r) -正交因子分解(英文)

设图G的顶点集为V(G) ,边集为E(G) ,g和f是定义在V(G)上的 2个整值函数 ,满足对于一切x∈V(G) ,g(x)≤f(x) .若G是一个 (mg +rn ,mf-rn) -图 ,1≤n <m ,r≥ 2 ,且对于x∈V(G) ,有g(x)≥k≥ 1,则存在G的一个子图G′ ,使得G′具有一个 (f,g) -因子 (n ,r) -正交于G的任意给定子图H ,其中 |E(H) |=nk .

工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是:给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。

锥预不变凸映射的Pareto极小问题

利用锥预不变凸映射的性质和数值化方法,研究一类锥预不变凸映射的Pareto极小问题,得到此类问题的Lagrange函数的鞍点、最优性条件、对偶问题及其解的存在定理。

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列L,证明了二元均衡排序的PoA的紧界为8/7。如果工件尺寸在区间[1,r](r≥1)内,得到了二元均衡排序的PoA的紧界为关于r的分段线性函数。

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器(分别称为机器M1和M2)上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择:模式1是将两个任务都安排在机器M2上加工;模式2是将任务A和B分别安排在机器M1和M2上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.

带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法

k-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有k种不同的产品,每一客户均需要k种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有k个设施来为其提供k种不同的产品,使得设施建设费用与运输费用之和最小。对于k-种产品设施选址问题,我们通常简写为k-PUFLP,其中,当所有设施建设费用为0时,记为k-PUFLPN。本文对k-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当k≥3时分析算法将k-PUFLPN的近似比从3k/2-1提升到了3k/2-3/2。鲁棒k-种产品设施选址问题是指在该问题中,最多有q个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒k-种产品选址问题建立模型,当k≥3,得到了3k/2-3/2近似算法。对顾客伴有线性惩罚的鲁棒k-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用k-PUFLPN中最优整数解与最优分数解的关系,得到了3k/2-3/2近似算法。

工件具有相似加工时长时两台机上LPT算法的性能分析

本文研究了工件具有相似加工时长时2台同类型平行机上LPT算法的最坏性能比。目标函数是使所有机器的最大完工时间达到最小。若工件序列L={J1,J2,...,Jn}中的工件满足pj∈[1,r](r≥1),证明了LPT算法的最坏性能比为r的分段线性函数,此结论改进了已有的最好结论,并且是不能再改进的最好结论。

同类机上工件实时到达在线排序问题

同类机上工件实时到达的在线排序问题是给定m台分别具有加工速度S1,S2,&#183;&#183;&#183;,Sm的同类机器M1,M2,&#183;&#183;&#183;,Mm及实时到达的工件序列L=﹛J1,J2,&#183;&#183;&#183;,Jn﹜,目标函数是最小化机器的最大完工时间,本文研究了S1=S2=&#183;&#183;&#183;=Sm-1=1, Sm 】1时同类机上工件实时到达的在线排序问题的LS算法,给出并证明了LS算法的最坏性能比。

Horn函数可满足性的复杂性(英文)

本文证明了 Ｈｏｒｎ函数的极大可满足性即使是限制在如下两种情况中的任何一种也是 ＭＡＸ ＳＮＰ困难的，第一种情况是每个公式都是二次的，第二种是公式中每一个非单位子句有且只有一个补元，这意味着在这档两种情况下没有多项式的近似算法，除非Ｐ＝ＮＰ．