求解非增次模集函数最大值问题的近似算法及其性能保证

次模集函数的最值问题在组合优化问题中有广泛的应用,给出了求解非增次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证.     

求解多维约束下下模函数最大值的改进贪婪算法

提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.     

Hoffman-Wielandt定理的推广及应用

1　引言及记号用 Rn× n表示所有 n× n阶实矩阵的集合 ,用 Sn× n,Sn× n+及 Sn× n++分别表示所有 n×n实对称矩阵 ,实对称半正定矩阵及实对称正定矩阵的集合 ,用 Tr(M)表示矩阵 M的迹 ,对 A,B∈ Rn× n.定义其内积为 A×B=Tr(ATB) .考虑如下半正定线性互补问题 :求 X,Y∈ Sn× n使Y =L (X) +Q,X≥ O,Y≥ O,X× Y =0 ,(1)其中 Q∈ Sn× n,L :Sn× n→ Sn× n为线性算子 ,而 X≥ O表示 X∈ Sn× n+(O表示零矩阵 ) .若 L:Sn× n→Sn× n满足X× L (X)≥ 0 ,　　 X∈ Sn× n. (2 )则称其为单调算子 ,而相应的问题称为单…     

Sm ∨ Kn,n的边色数和均匀全色数

本文得到了m 1阶星和完全等二部图联图的边色数和均匀全色数.     

求解一类非单调线性互补问题的路径跟踪法及其计算复杂性

１．引言及记号 线性互补问题的一般形式是;求（ｘ,ｓ） 　　　　　　　 使其中 众所周知,当Ω＋非空时,单调线性互补问题可在多项式时间内求解,而且人们已经设计出了多种求解单调线性互补问题的有效的内点算法（见［１］和［７］）．然而,对于求解非单调线性互补问题的内点算法的研究可以说才刚刚开始．文［２］讨论了当Ｍ为Ｐ矩阵时问题（１）的中心路径的存在唯一性;文［３］给出了设计求解一类非单调线性互补问题的内点算法的一般框架;文［４］给出了求解一类非单调线性互补问题的一种势能函数约减法并讨论了其算法的计算复杂…     

求解非减上模集函数最小值问题的近似算法及其性能保证

上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.     

求解互补问题的不可行内点法及其计算复杂性

给出了求解一类非单调非线性互补问题的一种不可行内点法,讨论了该算法的收敛性及计算复杂性.分析结果表明,所给方法是一多项式时间算法.