来自采访:删除 n×n 矩阵中的行和列以最大化剩余值的总和 [英] From an interview: Removing rows and columns in an n×n matrix to maximize the sum of remaining values

问题描述

给定一个 n×n 实数矩阵.您可以擦除任意数量(从 0 到 n)的行和任意数量(从 0 到 n)的列，然后计算剩余条目的总和.想出一个算法，找出要擦除哪些行和列，以最大化该总和.

Given an n×n matrix of real numbers. You are allowed to erase any number (from 0 to n) of rows and any number (from 0 to n) of columns, and after that the sum of the remaining entries is computed. Come up with an algorithm which finds out which rows and columns to erase in order to maximize that sum.

推荐答案

问题是 NP-hard.(所以你不应该指望有一个多项式时间算法来解决这个问题.不过，仍然可能有(非多项式时间)算法比蛮力稍微好一点.) NP-hardness 证明背后的想法是如果我们能解决这个问题，那么我们就可以解决一般图中的团问题.(最大集团问题是在图中找到最大的成对连接顶点集.)

The problem is NP-hard. (So you should not expect a polynomial-time algorithm for solving this problem. There could still be (non-polynomial time) algorithms that are slightly better than brute-force, though.) The idea behind the proof of NP-hardness is that if we could solve this problem, then we could solve the the clique problem in a general graph. (The maximum-clique problem is to find the largest set of pairwise connected vertices in a graph.)

具体来说，给定任何具有 n 个顶点的图，让我们形成矩阵 A，其中条目 a[i][j] 如下:

Specifically, given any graph with n vertices, let's form the matrix A with entries a[i][j] as follows:

• a[i][j] = 1 for i == j(对角线条目)
• a[i][j] = 0 如果边 (i,j) 存在于图中(并且 i≠j)
• a[i][j] = -n-1 如果边 (i,j) 不出现在图中.

• a[i][j] = 1 for i == j (the diagonal entries)
• a[i][j] = 0 if the edge (i,j) is present in the graph (and i≠j)
• a[i][j] = -n-1 if the edge (i,j) is not present in the graph.

现在假设我们解决了移除一些行和列(或等效地保留一些行和列)的问题，以便矩阵中条目的总和最大化.那么答案给出了图中最大的clique:

Now suppose we solve the problem of removing some rows and columns (or equivalently, keeping some rows and columns) so that the sum of the entries in the matrix is maximized. Then the answer gives the maximum clique in the graph:

1. 声明:在任何最佳解决方案中，没有保留边 (i,j) 不在图中.证明:由于 a[i][j] = -n-1 并且所有正项的总和最多为 n，选择 (i,j) 将导致为负数.(请注意，删除所有行和列会得到更好的总和，即 0.)

1. Claim: In any optimal solution, there is no row i and column j kept for which the edge (i,j) is not present in the graph. Proof: Since a[i][j] = -n-1 and the sum of all the positive entries is at most n, picking (i,j) would lead to a negative sum. (Note that deleting all rows and columns would give a better sum, of 0.)

声明:在(某些)最优解决方案中，保留的行和列集是相同的.这是因为从任何最佳解决方案开始，我们可以简单地删除所有没有保留列 i 的行 i，反之亦然.请注意，由于唯一的正项是对角线项，因此我们不会减少总和(根据前面的说法，我们也不会增加总和).

Claim: In (some) optimal solution, the set of rows and columns kept is the same. This is because starting with any optimal solution, we can simply remove all rows i for which column i has not been kept, and vice-versa. Note that since the only positive entries are the diagonal ones, we do not decrease the sum (and by the previous claim, we do not increase it either).

所有这些都意味着，如果图的最大集团大小为 k，那么我们的矩阵问题有一个和 k 的解决方案，反之亦然.因此，如果我们可以在多项式时间内解决我们的初始问题，那么集团问题也将在多项式时间内解决.这证明最初的问题是NP-hard.(实际上，很容易看出初始问题的决策版本——有没有办法去除一些行和列，使总和至少为 k——在 NP 中，所以 (该) 初始问题的决策版本实际上是 NP-complete.)

All of which means that if the graph has a maximum clique of size k, then our matrix problem has a solution with sum k, and vice-versa. Therefore, if we could solve our initial problem in polynomial time, then the clique problem would also be solved in polynomial time. This proves that the initial problem is NP-hard. (Actually, it is easy to see that the decision version of the initial problem — is there a way of removing some rows and columns so that the sum is at least k — is in NP, so the (decision version of the) initial problem is actually NP-complete.)

这篇关于来自采访:删除 n×n 矩阵中的行和列以最大化剩余值的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！