最大的非连续全1子矩阵

Question

我正在解决一个问题：找到一个最大尺寸的布尔矩阵非连续子矩阵，使得其中的所有单元都是1。

以以下矩阵为例：

M = [[1, 0, 1, 1],
     [0, 0, 1, 0],
     [1, 1, 1, 1]]

M的一个非连续子矩阵由一组行R和一组列C指定。子矩阵由所有在R中的某些行且在C中的某些列（即R和C的交集）中的单元格组成。请注意，非连续子矩阵是子矩阵的概括，因此任何（连续）子矩阵也是非连续子矩阵。

M中有一个最大的非连续子矩阵，其所有单元格均为1。此子矩阵定义为R = {1, 3, 4}和C = {1, 3}，其结果如下：

M[1, 2, 4][1, 3] = [[1, 1, 1],
                    [1, 1, 1]]

我在查找关于这个问题的现有文献时遇到了困难。我正在寻找高效算法，它们不一定需要是最优的（因此我可以将问题放松到找到最大尺寸的子矩阵）。当然，这可以用整数线性规划来建模，但我想考虑其他选择。

特别地，我想知道这个问题是否已经为学术界所知，并且我想知道我的非连续矩阵的定义是否合理，以及是否已经存在另一个名称。

谢谢！

- Gonzalo Solera

---

您所考虑的最大矩阵尺寸是多少？您有特定的时间限制吗？ - Damien

矩阵的大小将为50x50，尽管我也对一般情况下高效的算法感兴趣。时间限制应该在0.1秒左右，尽管我对此有弹性。 - Gonzalo Solera

这是最大边双团问题，是NP难问题。我作为评论发布，因为我手头没有算法建议。 - David Eisenstat

我听说过这种子矩阵被称为“矩形”。我在“矩形覆盖数”的背景下遇到了它。也许这样可以更容易地找到相关文献。（我会在“矩形覆盖数”的背景下寻找） - Josef Wittmann

非常感谢@DavidEisenstat！我并不一定需要一个算法，因为知道这个问题是NP难的，这使我可以专注于启发式算法和贪心算法。所以如果您将此评论作为答案发布，我将接受它。我还在https://mathematica.stackexchange.com/questions/190162/finding-the-largest-rectangular-submatrix中找到了一些信息，您也可以在答案中链接它。非常感谢！ - Gonzalo Solera

@JosefWittmann 实际上，我想要解决的根本问题是矩形覆盖数量。我不知道它的存在，非常感谢你，这对我非常有帮助。 - Gonzalo Solera

Answer 1

鉴于您对Josef Wittmann的评论做出回应，希望找到矩形覆盖数，我的建议是构建Lovász-Saks图并应用图着色算法。

Lovász-Saks图中每个1矩阵元素都有一个顶点，且包含0的2x2矩阵的每一对顶点之间都有一条边。在您的示例中，

[[1, 0, 1, 1],
 [0, 0, 1, 0],
 [1, 1, 1, 1]]

我们可以用字母标记1s：

[[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.

- David Eisenstat

---

谢谢你的回答！我想知道是否贪心地迭代地找到最大的1矩形，直到所有的1都被覆盖，会导致矩形覆盖数。即，如果我们找到最大的1矩形并将其更改为零，重复此过程直到没有1剩余，则迭代次数等于矩形覆盖数。我猜想这是正确的，尽管我还没有找到证明。 - Gonzalo Solera

算了，这不是真的，因为我找到了一个反例： [[1 1 0], [1 1 1], [0 1 1]] - Gonzalo Solera

我仍然想知道该过程是否会产生尽可能少的非重叠1矩形覆盖（不是矩形覆盖数，因为不允许矩形重叠）。 - Gonzalo Solera

没关系，我自己找到了一个（非平凡的）反例来回答 :) - Gonzalo Solera

@GonzaloSolera 你可以枚举所有的双团，然后使用贪心策略或编写精确覆盖整数规划来解决问题。 - David Eisenstat