论文标题
用于矩阵完成的参数化算法具有半径约束
Parameterized Algorithms for Matrix Completion With Radius Constraints
论文作者
论文摘要
考虑到缺少条目的矩阵，我们研究了NP-硬矩阵完成问题，在这些问题中，所得完成的矩阵的半径为有限（局部）半径。在纯半径版本中，这意味着目标是填充条目，以使“中心字符串”具有与所有矩阵行尽可能小的锤击距离。 In stringology, this problem is also known as Closest String with Wildcards. In the local radius version, the requested center string must be one of the rows of the completed matrix. Hermelin and Rozenberg [CPM 2014, TCS 2016] performed parameterized complexity studies for Closest String with Wildcards.我们回答了他们的一个空旷问题，请修复有关固定参数障碍性的错误导致他们的工作，并改善某些上限运行时间范围。 For the local radius case, we reveal a computational complexity dichotomy. In general, our results indicate that, although being NP-hard as well, this variant often allows for faster (fixed-parameter) algorithms.
Considering matrices with missing entries, we study NP-hard matrix completion problems where the resulting completed matrix shall have limited (local) radius. In the pure radius version, this means that the goal is to fill in the entries such that there exists a 'center string' which has Hamming distance to all matrix rows as small as possible. In stringology, this problem is also known as Closest String with Wildcards. In the local radius version, the requested center string must be one of the rows of the completed matrix. Hermelin and Rozenberg [CPM 2014, TCS 2016] performed parameterized complexity studies for Closest String with Wildcards. We answer one of their open questions, fix a bug concerning a fixed-parameter tractability result in their work, and improve some upper running time bounds. For the local radius case, we reveal a computational complexity dichotomy. In general, our results indicate that, although being NP-hard as well, this variant often allows for faster (fixed-parameter) algorithms.
