从采访中：删除的行和列在一个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难。 （因此，你不应该期望一个多项式时间算法用于解决该问题，有可能仍是（非多项式时间）算法，它们比蛮力稍好，虽然。）NP难度的证明背后的想法是，如果我们能解决这个问题，那么我们就可以解决的派系问题的。 （最大-团问题是要找到的在图中成对连接的顶点的最大集合。）

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 [1] [J] 如下：

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

• A [1] [J] = 1 为我==Ĵ（对角线项）
• A [1] [J] = 0 如果边（i，j）为图中的present（和我≠Ĵ）
• A [1] [J] = -n-1 如果边（i，j）为的没有的present在的曲线图。

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

现在假设我们解决除去一些行和列的问题（或等同地，<强>保持一些行和列），以便在矩阵中的条目的总和被最大化。那么答案给出了最大团中图：

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）不present在曲线图。证明：由于 A [1] [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.)

要求：在（一些）最优解，设定的行和列的保持是一样的。这是因为在开始任何最佳的解决方案，我们可以简单地删除所有行我为这列我未保持，反之亦然。注意，由于仅正项是对角的，我们不减少的总和（和由previous权利要求，我们不增加它要么）

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难。 （其实，这是不难看出，最初的问题的决策版本 - 有没有删除一些行和列的方式，使之和至少 K - 是在NP，所以最初的问题（的决定版）实际上是 NP完全。 ）

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屋！