具有给定稀疏矩阵的求解向量最小化矩阵向量积的最优算法

Question

如果A，是一个包含36列和n行的二进制值稀疏矩阵(其中每一行都是随机的，每个行都有至少1行和最多12行的约束)，那么是否有可能找到一种最优策略来创建二进制值的列向量(精确为12 1和24 0)，这样n by 1列向量b = Ax的每一行都包含一个实数(包含0到12之间的一个数字)，其最大值尽可能小吗？

我在优化问题的这个子集上遇到了麻烦，我一直试图强行强迫它，但没有效果(通过为x).生成和测试伪随机数)。这个任务真的很难吗，还是我只是想的不够？

Answer 1

对于这个问题有一个O(二项式( 36，12) n) = O(n)时间算法，但是把36推广到m，有一个从独立集到这个问题的多项式时间约简，它显示出NP-硬度。(想法:给定一个图，发出它的邻接矩阵，但是在对角线上。)我们可以设置为1而不导致无穷范数超过1的最大向量项数等于最大独立集的大小。图可以假定为立方体，以便处理行上L1规范约束的更严格版本。)

36 seem 12还不到13亿，这看起来并不多，但你也可以尝试通过整数规划来解决这个问题，因为整数程序求解者通常擅长于这类包装问题。(如果你需要推荐，我会在工作中使用或工具，并对此感到非常满意。)