摘要：本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率(γ),我们设计了单轮读取数据的过滤-流算法,并结合次模、超模函数的全局曲率(κ^(g))得到算法的近似比为min{(1-ε)γ/2γ),1-γ/2γ(1-k^(g)^(2))}。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出:次模函数和超模函数在同量级条件下,能保证在较少的时间内得到与贪婪算法相同的最优值。

摘要：经典k-均值问题是一类应用广泛的聚类问题,它是指给定R^(d)中观测点集合D和整数k,目的是在空间中寻找k个点作为中心集合S,使得集合D中的每个观测点到S中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典k-均值问题有很多推广,本文研究的带惩罚的相同容量k-均值问题就是其中之一。与经典k-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接U个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取(3+α)k个中心的情况下,可以达到β-近似,其中,参数α>34,β>α+34/α-34。