Maximum rank matrix completion

被引：32

作者：

Geelen, JF ^{[1
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 1999年 / 288卷 / 1-3期

关键词：

matrix completion;

D O I：

10.1016/S0024-3795(98)10210-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The maximum rank completion problem is the problem of, given a partial matrix (that is, a matrix where we are only given some of the entries), filling in the unknown entries in such a way as to maximize the rank. Applications include bipartite matching and matroid intersection for linearly represented matroids. We describe an algorithm that finds a maximum rank completion by perturbing an arbitrary completion in a greedy way. (C) 1999 Elsevier Science Inc. All rights reserved.

引用

页码：211 / 217

页数：7