相等的双目录分割问题及其随机算法  

Equivalent 2-Catalog Segmentation Problem and It’s Improved Randomized Algorithm

作　　者：袁玉波[1] 溥冬梅[1] 

机构地区：[1]电子科技大学应用数学学院,四川成都610054

出　　处：《宁夏大学学报（自然科学版）》2005年第1期34-37,共4页Journal of Ningxia University(Natural Science Edition)

基　　金：电子科技大学青年基金重点资助项目(JX04042)

摘　　要：研究了相等的双目录分割问题,给出了此问题的随机算法.通过分析算法的性能,得到算法的近似性能比为0.637 8.在回答Jon Kleinberg于1998年提出的一个公开问题方面取得了一定进展.In this paper an improved randomized algorithm of the equivalent 2-catalog segmentation problem is presented. Some progresses to answer the open problem are made by analyzing this algorithm with performance guarantee. A 0.6378-approximation for the equivalent 2-catalog segmentation problem is (obtained.)

关 键 词：数据挖掘 分割 组合优化 近似算法 半正定规划 

分 类 号：O221.2[理学—运筹学与控制论]