Algorithm for quadratic semi-assignment problem with partition size coefficients

This paper discusses the problem of assigning $N$ streams of requests (clients) to $M$ related server machines with the objective to minimize the sum of worst-case processing times. The completion time of a batch of requests is measured as a sum of weights of the subset of clients which share a single machine. Such problem can be seen as minimizing the sum of total weights of blocks of $M$ -partition, each multiplied by the cardinality of a block. We prove that this problem can be solved in polynomial time for any fixed $M$ and present an efficient backward induction algorithm.