k-平均问题及其变形的算法综述

k-平均问题是计算机科学和组合优化领域的经典问题之一.k-平均聚类作为最受重视而且最简单易懂的一种聚类分析方法流行于数据挖掘领域.k-平均问题可描述为:给定n个元素的观测集,其中每个观测点都是d维实向量,目标是把这n个观测点划分到k(≤n)个集合中,使得所有集合中的点到对应的聚类中心的距离的平方和最小,其中一个集合的聚类中心指的是该集合中所有观测点的均值.k-平均问题在理论上是NP-难的,但有高效的启发式算法,广泛应用在市场划分、机器视觉、地质统计学、天文学和农业等实际背景中.随着实际问题中遇到的k-平均问题更加复杂,数据量更加庞大,还需学者进行更深一步的研究.罗列出k-平均问题及其诸多变形及推广问题的经典算法,并总结k-平均中尚待研究的若干问题.     

k-均值算法的初始化方法综述

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注, 是经典的NP-难问题之一. 给定N个d维实向量构成的观测集, 目标是把这N个观测点划分到k(\leq N)个集合中, 使得所有集合中的点到对应的聚类中心距离的平方和最小, 一个集合的聚类中心指的是该集合 中所有观测点的均值. k-均值算法作为解决k-均值问题的启发式算法,在实际应用中因其出色的收敛速度而倍受欢迎. k-均值算法可描述为: 给定问题的初始化分组, 交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解. 该算法通常被认为几乎是线性收敛的. 但缺点也很明显, 无法保证得到的是全局最优解, 并且算法结果好坏过于依赖初始解的选取. 于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量. 现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.     

κ-均值算法的初始化方法综述

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注,是经典的NP-难问题之一.给定N个d维实向量构成的观测集,目标是把这N个观测点划分到k(≤N)个集合中,使得所有集合中的点到对应的聚类中心距离的平方和最小,一个集合的聚类中心指的是该集合中所有观测点的均值.k-均值算法作为解决k-均值问题的启发式算法,在实际应用中因其出色的收敛速度而倍受欢迎.k-均值算法可描述为:给定问题的初始化分组,交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解.该算法通常被认为几乎是线性收敛的.但缺点也很明显,无法保证得到的是全局最优解,并且算法结果好坏过于依赖初始解的选取.于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量.现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.     

带集合约束的分布式随机凸优化

本文研究了一个受集合约束的优化问题:minΣ~N_(i=1)f_i(x),s.t.x∈X,提出了一个基于多智能体系统的算法来求解这个问题.每个自主体i有其自身的一个局部目标函数f_i(x)以及全局约束集X.通过与相邻自主体的通信,每个自主体都能获取局部信息用来实现分布式控制律.本文证明了在所设计的分布式控制律的作用下,每个自主体的状态最终趋于一致并进入到全局目标函数的最优解集中,同时也满足约束x∈X.在大多数已有的算法里,每个自主体在每个采样时刻都需要进行以下的计算:(1)约束集投影;(2)次梯度搜索;(3)加权平均.然而在本文所提出的算法中,每个自主体在每个采样时刻只需要随机进行:(1)保持当前状态;(2)约束集投影;(3)次梯度搜索中的一项计算,然后再与相邻自主体的信息进行加权平均.与传统的确定性算法相比,本文的所提出的算法降低了每个采样时刻各个自主体的计算量.     

高校应用数学学报第19卷(2004年)B辑(英文版)第3期目次和提要

将小直径图划分为导出匹配杨爱峰　原晋江(郑州大学数学系)给定一个简单图G和一个正整数k,是否存在V( G)的一个k-划分( V1,V2 ,…,Vk)使得每个导出子图G[Vi]是1 -正则的?称该问题为导出匹配k-划分问题.该文对小直径图研究该问题的计算复杂性.证明了直径为6的图的导出匹配2 -划分问题和直径为2的图的导出匹配3-划分问题是NP-完全的,而直径为2的图的导出匹配2 -划分问题是多项式时间可解的.外来的捕食物种对濒危物种的影响张少林(浙江科技学院)研究了从保护生态学中提出的一个重要问题:引入的物种如何通过捕食影响本地物种的持续生存?应用…     

抽屉原理

抽屉原理俗称鸽巢原理,又叫狄利克雷原理.简单地说就是:把3个苹果放入两个抽屉中,必有一个抽屉中至少有两个苹果;把3个苹果放入4个抽屉中,必有一个抽屉中没有苹果.1抽屉原理的几种形式1)第一抽屉原理(少的抽屉原理)设有m个元素分属于n个集合(其两两的交集可以非空),且m>kn(m,n,k均为正整数),则必有一个集合中至少有k 1个元素.2)第二抽屉原理(多的抽屉原理)设有m个元素分属于n个两两不相交的集合,且m相似文献   

Halin图的线性k-点荫度

图G的线性点荫度vla(G)是指V(G)的最小划分数,使得每个点划分集的导出子图为线性森林.G的线性k-点荫度vla_k(G)是指V(G)的最小划分数,使得每个点划分集的导出子图的每个连通分支为长度至多为k的路.1998年,吴建良证明了Halin图的线性点荫度为2.本文在此基础上,证明了对Halin图G,有vla_k(G)=2,其中■     

闭凸集约束下线性矩阵方程求解的松弛交替投影算法

研究线性矩阵方程AXB=C在闭凸集合R约束下的数值迭代解法.所考虑的闭凸集合R为(1)有界矩阵集合,(2)Q-正定矩阵集合和(3)矩阵不等式解集合.构造松弛交替投影算法求解上述问题,并用算子理论证明了由该算法生成的序列具有弱收敛性.给出了矩阵方程AXB=C求对称非负解和对称半正定解的数值算例,大量数值实验验证了该算法的可行性和高效性,并说明该算法与交替投影算法和谱投影梯度算法比较在迭代效率上的明显优势.     

带惩罚的相同容量k-均值问题的局部搜索算法

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

带惩罚的相同容量k-均值问题的局部搜索算法

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

Lower bounds and modified LPT algorithm for k-partitioning problems with partition matroid constraint

In this paper,the k-partitioning problem with partition matroid constraint is consid- ered.LPT algorithm is modified to fit the problem and its worst-case performance is analyzed. The lower bounds of optimal solution for the min-max problem are given.     

一类人员招聘问题的算法研究

在人员招聘工作中,通常有招聘总人数和各部门最低录取人数要求等限制。针对给定的限制条件,本文给出了一类人员招聘问题的数学模型。考虑招聘过程中固定指标为0和机动指标为0的特殊情形,分别给出了相应模型的贪婪算法和匈牙利指派算法,在此基础上给出了求解该问题的一种基于指派问题的一般算法,并对相应的算法的最优性给出了证明,算法的复杂度仅为O(m3)。以公务员招聘的实际算例验证,模型能合理地满足招聘单位的实际需求。     

Minimum cost flow algorithms for series-parallel networks

It is shown that an acyclic multigraph with a single source and a single sink is series-parallel if and only if for arbitrary linear cost functions and arbitrary capacities the corresponding minumum cost flow problem can be solved by a greedy algorithm. Furthermore, for networks of this type with m edges and n vertices, two O(mn+logm)-algorithms. One of them is based on the greedy scheme.     

考虑商品数量和商品拣选成本的AGV智能仓库订单分批问题研究

AGV(Automated Guided Vehicle,自动导引车)智能仓库是一种基于“货到人”拣选模式的自动化仓库。本文考虑了订单中商品的需求量和货架上商品的存储量,以极小化货架搬运成本和商品拣选成本为目标,建立了AGV智能仓库订单分批问题的整数规划模型。本文针对订单分批问题的特点,提出了一种基于订单和货架交替选择的贪婪求解算法。对比CPLEX求解器的精确最优解,本文提出的贪婪算法的误差百分比不超过10%,平均误差百分比为5.38%;对比基于相似性的分批算法的求解结果,本文提出的贪婪算法不仅运算时间更短,解的质量也更好。进一步地,对比不考虑商品拣选成本的订单分批模型,本文提出的模型在不明显增加货架搬运成本的前提下,可以大幅度降低商品拣选成本。因此,在订单分批模型中考虑商品拣选成本是非常必要的。     

Optimization over the polyhedron determined by a submodular function on a co-intersecting family

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.     

An exact algorithm for solving the bilevel facility interdiction and fortification problem

We present an exact approach for solving the $r$-interdiction median problem with fortification. Our approach consists of solving a greedy heuristic and a set cover problem iteratively that guarantees to find an optimal solution upon termination. The greedy heuristic obtains a feasible solution to the problem, and the set cover problem is solved to verify optimality of the solution and to provide a direction for improvement if not optimal. We demonstrate the performance of the algorithm in a computational study.     

On the construction of bodies of constant width containing a given set

We discuss the problem of sparse representation of domains in ℝ ^d . We demonstrate how the recently developed general theory of greedy approximation in Banach spaces can be used in this problem. The use of greedy approximation has two important advantages: (1) it works for an arbitrary dictionary of sets used for sparse representation and (2) the method of approximation does not depend on smoothness properties of the domains and automatically provides a near optimal rate of approximation for domains with different smoothness properties. We also give some lower estimates of the approximation error and discuss a specific greedy algorithm for approximation of convex domains in ℝ².     

A Greedy Algorithm for Capacitated Lot-Sizing Problems

We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid. We present a greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm in O ( n ) time.     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.     

On some new types of greedy chains and greedy linear extensions of partially ordered sets

Two new types of greedy chains, strongly and semi-strongly greedy, in posets are defined and their role in solving the jump number problem is discussed in this paper. If a poset P contains a strongly greedy chain C then C may be taken as the first chain in an optimal linear extension of P. If a poset P has no strongly greedy chains then it contains an optimal linear extension which starts with a semi-strongly greedy chain. Hence, every poset has an optimal linear extension which consists of strongly and semi-strongly greedy chains. Algorithmic issues of finding such linear extensions are discussed elsewhere (Syslo, 1987, 1988), where we provide a very efficient method for solving the jump number problem which is polynomial in the class of posets whose arc representations contain a bounded number of dummy arcs. In another work, the author has recently demonstrated that this method restricted to interval orders gives rise to 3/2-approximation algorithm for such posets.