New answers tagged

2

As kcsquared notes, this is an instance of integer linear programming (ILP) in two dimensions. Lenstra showed that ILP can be solved in polynomial time when the number of dimensions is constant; the special case of two dimensions was apparently proven earlier by Scarf. This proves that your program can be solved in polynomial time, as you were hoping.


2

The problem can be shown to be weakly NP-hard by noticing that it is a generalization of partition. In particular, when $m=2$ the input set of integers is a yes instance of partition if and only if the measure of an optimal solution of your problem equals half the sum of the integers. The problem can also be shown to be strongly NP-hard by noticing that it ...


Top 50 recent answers are included