| 秩约束子集选择问题的分而治之解法 |
| |
| 引用本文： | 张振跃,叶环球. 秩约束子集选择问题的分而治之解法[J]. 计算数学, 2002, 24(2): 229-242 |
| |
| 作者姓名： | 张振跃 叶环球 |
| |
| 作者单位： | 浙江大学玉泉校区数学系,杭州,310027 |
| |
| 基金项目： | 国家重点基础研究专项经费（G19990328），教育部高校骨干教师基金资助． |
| |
| 摘 要： | We consider the rank-constrained subset selection problem(RCSS):Given a matrix A and integer p≤rank(A),fing the largest submatrix A0 consisting of some colmns of A with rank(A0)=p.The RCSS problem is generally NP-hard.This paper focuses on a divide-and -conquer(DC)algorithm for solving the RCSS problem:Partition the matrix A into several small column blocks:A∏=[A1,…,Ak] with a certain column permutation ∏and decompose p to p1 p2 …pk such that solutions of the RCSS problems for smaller couples form a solution of the original RCSS problem.We show that the optimal solution of the RCSS problem can be found by DC algorithm for eachP≤rank (A),if and only if A is column-partitionable,i.e.,rank(A)=∑i=1^k rank(Ai),Based upon QR decomposition,a fast algorithm for determining the column partition is offered. Our divide-and-conquer algorithm is also quite efficient even A is approximately column-partitionable.
|
| 关 键 词： | 秩约束 子集选择问题 分而治之解法 信息检索 列可分矩阵 整数规划 计算机信息处理 |
| 修稿时间： | 2001-04-27 |
A DIVIDE-AND-CONQUER ALGORITHM FOR THE RANK-CONSTRAINED SUBSET SELECTION PROBLEM |
| |
| Affiliation: | Zhang Zhenyue, Ye Huanqiu (Department of Mathematics, Zhejiang University, Yuquan Campus, Hangzhou, 310027) |
| |
| Abstract: | |
| |
| Keywords: | information retrieval divide-and-conquer algorithm sub- set selection column- Partitionable matrix |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算数学》浏览原始摘要信息 |
|
点击此处可从《计算数学》下载全文 |
|
