The Complexity of Vector Partition
share
We consider the vector partition problem, where n agents, each with a d-dimensional attribute vector, are to be partitioned into p parts so as to minimize cost which is a given function on the sums of attribute vectors in each part. The problem has applications in a variety of areas including clustering, logistics and health care. We consider the complexity and parameterized complexity of the problem under various assumptions on the natural parameters p,d,a,t of the problem where a is the maximum absolute value of any attribute and t is the number of agent types, and raise some of the many remaining open problems.
READ FULL TEXT