全1的最大非连续子矩阵
Biggest non-contiguous submatrix with all ones
我正在解决寻找具有最大尺寸的布尔矩阵的非连续子矩阵的问题，这样它的所有单元格都是一个。
例如，考虑以下矩阵：
M = [[1, 0, 1, 1],
[0, 0, 1, 0],
[1, 1, 1, 1]]
M的非连续子矩阵指定为一组行R和一组列C。子矩阵由R中某行中的所有单元格组成and 在 C 的某些列中（R 和 C 的交集）。请注意，非连续子矩阵是子矩阵的推广，因此任何（连续）子矩阵也是非连续子矩阵。
M的一个最大不连续子矩阵，其所有单元格都为1。此子矩阵定义为 R={1, 3, 4} 和 C={1, 3}，它产生：
M[1, 2, 4][1, 3] = [[1, 1, 1],
[1, 1, 1]]
我很难找到有关此问题的现有文献。我正在寻找不一定需要最优的高效算法（这样我就可以将问题放宽到找到最大尺寸的子矩阵）。当然，这可以用整数线性规划建模，但我想考虑其他替代方案。
特别是，我想知道这个问题是否已经为人所知并被文献涵盖，我想知道我对非连续矩阵的定义是否有意义，以及它们是否已经存在不同的名称。
谢谢！
根据您对 Josef Wittmann 的评论的回复，您想要找到矩形覆盖数，我的建议是构建 Lovász–Saks 图并应用图着色算法。
Lovász–Saks 图矩阵中的每一个条目都有一个顶点，每对顶点之间有一条边，其 2x2 矩阵包含一个零。在你的例子中，
[[1, 0, 1, 1],
[0, 0, 1, 0],
[1, 1, 1, 1]]
我们可以用字母标记 1：
[[a, 0, b, c],
[0, 0, d, 0],
[e, f, g, h]]
然后获取边
a--d, a--f, b--f, c--d, c--f, d--e, d--f, d--h.
a b a 0 0 b b c 0 c 0 d 0 d d 0
0 d e f f g d 0 f h e f f g g h
我认为最佳着色是
{a, b, c, e, g, h} -> 1
{d} -> 2
{f} -> 3.
我正在解决寻找具有最大尺寸的布尔矩阵的非连续子矩阵的问题，这样它的所有单元格都是一个。
例如，考虑以下矩阵：
M = [[1, 0, 1, 1],
[0, 0, 1, 0],
[1, 1, 1, 1]]
M的非连续子矩阵指定为一组行R和一组列C。子矩阵由R中某行中的所有单元格组成and 在 C 的某些列中（R 和 C 的交集）。请注意，非连续子矩阵是子矩阵的推广，因此任何（连续）子矩阵也是非连续子矩阵。
M的一个最大不连续子矩阵，其所有单元格都为1。此子矩阵定义为 R={1, 3, 4} 和 C={1, 3}，它产生：
M[1, 2, 4][1, 3] = [[1, 1, 1],
[1, 1, 1]]
我很难找到有关此问题的现有文献。我正在寻找不一定需要最优的高效算法（这样我就可以将问题放宽到找到最大尺寸的子矩阵）。当然，这可以用整数线性规划建模，但我想考虑其他替代方案。
特别是，我想知道这个问题是否已经为人所知并被文献涵盖，我想知道我对非连续矩阵的定义是否有意义，以及它们是否已经存在不同的名称。
谢谢！
根据您对 Josef Wittmann 的评论的回复，您想要找到矩形覆盖数，我的建议是构建 Lovász–Saks 图并应用图着色算法。
Lovász–Saks 图矩阵中的每一个条目都有一个顶点，每对顶点之间有一条边，其 2x2 矩阵包含一个零。在你的例子中，
[[1, 0, 1, 1],
[0, 0, 1, 0],
[1, 1, 1, 1]]
我们可以用字母标记 1：
[[a, 0, b, c],
[0, 0, d, 0],
[e, f, g, h]]
然后获取边
a--d, a--f, b--f, c--d, c--f, d--e, d--f, d--h.
a b a 0 0 b b c 0 c 0 d 0 d d 0
0 d e f f g d 0 f h e f f g g h
我认为最佳着色是
{a, b, c, e, g, h} -> 1
{d} -> 2
{f} -> 3.