Algorithm for quadratic semi-assignment problem with partition size coefficients

Abstract

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.