Department of Computer Science & Engineering

In this paper we prove that the Divisible Load Scheduling (DLS) problem is NP-complete when the underlying distributed computing platform is a heterogeneous star network and when the costs for communicating and computing load chunks are affine functions of the chunk size. While the complexity of the DLS problem was known in the case of linear communication and computation costs (polynomial), or in the case of homogeneous platforms (polynomial), to the best of our knowledge it was still open for heterogeneous platforms with affine cost. We prove NP-completeness by reducing the DLS problem from 2-PARTITION, i.e., partition of a set of integer values into two sets whose sums are equal.

Pre-2018 CSE ID: CS2005-0818