Deterministic Polynomial Time Algorithms for Matrix Completion Problems

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e. the problem of assigning values to the v…