论文标题
在线总和优化
On Line Sum Optimization
论文作者
论文摘要
我们表明，找到$（0,1）$ - 矩阵的{\ em列总和优化问题}，具有规定的行总和，可以最大程度地减少给定函数的列列的评估总和，可以在多项式时间内求解，当所有函数都是相同的，或者当所有行总和都限制在所有函数时。我们推测，更通用的{\ em行总和优化问题}是找到一个矩阵最小化在其行总和和列总和上评估的给定函数的总和，也可以在多项式时间内解决。
We show that the {\em column sum optimization problem}, of finding a $(0,1)$-matrix with prescribed row sums which minimizes the sum of evaluations of given functions at its column sums, can be solved in polynomial time, either when all functions are the same or when all row sums are bounded by any constant. We conjecture that the more general {\em line sum optimization problem}, of finding a matrix minimizing the sum of given functions evaluated at its row sums and column sums, can also be solved in polynomial time.
