背包交拟阵约束下k-次模最大化问题.pdf

目录

中文摘要I

英文摘要II

第一章引言1

S带约束的次模函数最大化问题的研究背景和研究现状

S本文的主要工作

第二章背包交拟阵约束下次模最大化问题及近似算法6

S次模函数的性质

S背包和拟阵约束下次模最大化问题

第三章背包交拟阵约束下单调次模最大化问题分析10

S近似算法

S近似比分析

第四章背包交拟阵约束下非单调次模最大化问题分析27

S近似算法

S近似比分析

第五章可进一步研究的问题37

参考文献38

攻读硕士学位期间撰写或发表的学术论文42

攻读硕士学位期间参加的学术会议43

致谢44

山东师范大学硕士学位论文

背包交拟阵约束下k-次模最大化问题

于克敏

山东师范大学数学与统计学院,济南,山东,250358

摘要

次模函数是次模函数的一种推广仍保持边际效益递减性诸如带个主题

的影响最大化问题、种传感器放置问题都可以建模为带约束的次模函数最大

化问题而在本文中我们考虑了单背包交重拟阵约束下次模最大化问题针

对次模函数是否有单调性分别设计算法及分析近似比对于单调次模函数

本文提出了一个以局部有哪些信誉好的足球投注网站算法为主嵌套了贪婪算法的近似算法算法以枚举

有限多个最优解中的元素为初始解之后采用在算法解和最优解之间构造辅助

序列的分析方法最终得出1−−(+2)近似比其对应的枚举初始解的基数

+2

为≥+2面对非单调的次模函数我们在单调情况下的近似算法基础

+2−(+2)

上修改了枚举初始解的方式给出适用非单调情况的近似算法当次模函数失