【摘 要】
：
本论文主要研究带惩罚的动态设施选址问题及软容量约束的动态设施选址问题.由于该问题是NP困难的,我们考虑其近似算法的设计与分析.论文有如下两部分内容:
第一部分研究
论文部分内容阅读
本论文主要研究带惩罚的动态设施选址问题及软容量约束的动态设施选址问题.由于该问题是NP困难的,我们考虑其近似算法的设计与分析.论文有如下两部分内容:
第一部分研究带惩罚的动态设施选址问题.在该问题中给定若干时段,不同时段内设施的开放费用、用户的需求及连接费用不一定相同,而且允许用户的需求不被满足,但不满足的部分要有惩罚.利用原始对偶技巧,我们给出了该问题的3-近似算法.再运行贪婪增加程序后,近似比改进到1.8526.
第二部分研究软容量约束的动态设施选址问题.在该问题中每一个设施都是有软容量限制的.利用拉格朗日松弛技巧,我们给出了该问题的6-近似算法.运行贪婪增加程序后,近似比改进到3.7052.
其他文献
在第一章中，引入并研究了一类具有正系数解析函数类M+n（α，β）的特征，包含关系，系数估计，Hadamard卷积，偏差定理，覆盖定理以及（n，δ）-邻域问题.同时，还给出了关于Srivastava-Saigo-Owa分式
近年来,股票市场在我国发展迅速,已逐步成为金融企业必不可少的组成部分,受到投资者的普遍关注.但是股票市场的预测非常复杂和困难,需要通过预测股市波动的情况来把握股票市
在小学教育系统中,德育教育是一种关键的工作,小学生正处于身心发展初级阶段,启蒙教育的开展关系到他们一生的发展,德育教育直接关系到他们人生价值观的形成.因此,小学班主任
如今,篮球博彩市场发展迅猛,这使得篮球比赛胜负结果预测成为了一个新挑战。现有的篮球预测方法主要使用一些经典的统计学方法,如朴素贝叶斯分类器、逻辑斯蒂回归等,通过将篮
本文讨论二维不可压理想流体的两个方面.第一部分研究Euler系统中主要物理量即速度与压力梯度沿流线的演化情况，方法是从Euler方程推出这些量沿质点轨迹所满足的常微分方程，从
代数研究中常常考虑性质保持问题，比如群同态保持单位元，保持逆元等.在更一般范围上，比如范畴，加法范畴的局部化范畴仍然是加法范畴，Abelian范畴的局部化仍然是Abelian范畴.本文分
在中国文化产业盛况空前的今天,画坛上涌现出一大批优秀的书画人才。在这众多才子中我采访了著名画家郭晓恒。郭晓恒笔名“醉石”出生在一个书画世家,父亲郭振声笔名“殳耳”
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
本文主要研究一类带有疾病和HollingⅡ功能反应的捕食者-食饵扩散模型.全文共分七部分,首先,阐述了问题产生的背景.其次,通过线性化局部分析得到了系统非负平衡点的一致渐近
在参考文献[6]中,Burghelea和Haller定义了对称双线性挠率并且证明了该挠率的Anomaly公式的一个特殊情形。这个公式的一般情形后来在参考文献[21,Theorem2.1]中被陈述。根据