【摘 要】
：
设施选址问题和图划分问题是经典的NP-难问题,除非P=NP,否则这类问题不可能在多项式时间内求得最优解.设计近似算法是处理这类问题的重要方法之一.本论文研究随机优先设施选
论文部分内容阅读
设施选址问题和图划分问题是经典的NP-难问题,除非P=NP,否则这类问题不可能在多项式时间内求得最优解.设计近似算法是处理这类问题的重要方法之一.本论文研究随机优先设施选址问题,随机容错设施选址问题,和二目录分割问题.
在优先设施选址问题中,每个顾客有服务水平要求,每个设施开放费用关于服务水平单调递增.第2章,我们对随机优先设施选址问题设计了一个原始对偶3-近似算法,进一步结合贪婪增广的技巧将近似比改进到1.8526.
在容错设施选址问题中,为了防止已开放的设施出现故障从而导致顾客的服务无法满足,每个顾客要求连接到不止一个设施上.第3章,我们研究随机的容错设施选址问题.通过揭示随机问题的结构,并修改线性规划松弛的最优解,我们给出了基于线性规划舍入的5-近似算法.
二目录分割问题是图划分问题中重要问题之一.第4章,我们考虑二目录分割问题.对不相交的二目录分割问题,我们设计了基于非一致旋转和半定规划舍入的近似算法,刻画了近似比随半定规划最优值与总权重之间比值的变化曲线.曲线中最低点预示着该算法的近似比为0.7317,这是到目前为止该问题的最好的近似比.相应的,我们还研究了相交的二目录分割问题的近似比曲线.
其他文献
本文在比较的基础上分别从横向与纵向分析了国内外数学发展及其相关教育,希望能给新课程改革的数学课堂、课外的数学教育教学提供一些帮助。
On the basis of comparison, t
本文讨论了带移民的上临界分支过程的小值概率和连续状态分支过程的鞅收敛的Llog L准则,主要分成三部分。
第一部分讨论了带移民的上临界Galton-Watson过程的小值概率。
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
元胞自动机是定义在一个由有限离散状态的元胞构成的元胞空间上,每一个元胞都遵循着一定的局部规则来进行更新,并且它在时间和空间上都是离散的动力学系统。各个元胞在每个时
本文论述了主题图书馆的定义、建设意义、互联网+时代,并以鹰潭市道教主题图书馆的建设为案例进行分析,阐述了互联网+道教主题图书馆的实践意义与理论价值.
本论文主要研究一些Calabi-Yau三流形到S3×S3的连通和的锥形变换这个问题。
本论文的主要结果是：对每个Picard群的秩为2的光滑Fano4维环形簇X，X中处于一般位置的一个反典
随着全球金融市场特别是金融衍生品市场的迅猛发展,金融机构和投资者面临的各种风险日益复杂和多样化,因此对金融风险的评估和测量也提出了越来越高的要求。由于copula方法在
本文主要研究线性模型中最优线性无偏(BLu)估计和Bayes估计的优良性问题.全文分为四个部分. 第一部分介绍了最优线性无偏估计和Bayes估计理论的相关研究进展,并介绍了与本
三阶常微分方程在天文学和流体力学等学科的研究中有着广泛的应用。目前，对于三阶常微分方程采用Sinc离散的数值方法的研究并不多。由于Sinc方法具有较高的精度和能够处理奇异