Matrix Completion: Approximating the Minimum Diameter

Abstract

In this paper, we focus on the matrix completion problem and aim to minimize the diameter over an arbitrary alphabet. Given a matrix M with missing entries, our objective is to complete the matrix by filling in the missing entries in a way that minimizes the maximum (Hamming) distance between any pair of rows in the completed matrix (also known as the diameter of the matrix). It is worth noting that this problem is already known to be NP-hard. Currently, the best-known upper bound is a 4-approximation algorithm derived by applying the triangle inequality together with a well-known 2-approximation algorithm for the radius minimization variant. In this work, we make the following contributions: We present a novel 3-approximation algorithm for the diameter minimization variant of the matrix completion problem. To the best of our knowledge, this is the first approximation result that breaks below the straightforward 4-factor bound. Furthermore, we establish that the diameter minimization variant of the matrix completion problem is (2 − ε)-inapproximable, for any ε > 0, even when considering a binary alphabet, under the assumption that P ≠ NP. This is the first result that demonstrates a hardness of approximation for this problem.