Load-Balanced Parallel Solver for the Minimum k-Center and Related Problems

A. Černivec, D. Vladušič, and B. Slivnik (Slovenia)


minimum k-center, load balancing, generating combinations


A load-balanced exact solver for computing the exact solutions of minimum k-center and related facility locations problems, is described. To achieve the load balance on a dedicated multiprocessor system, i.e. a cluster or a super computer, a new algorithm for parallel generation of a set of all k-combinations of n-things (without repetitions) is introduced and analysed. We demonstrate that the new algorithm can also be used in a resource competitive environment if used or supplemented with a simple adaptive job scheduler. The solver is tested by producing the benchmarks for the minimum k-center problem.

Important Links:

Go Back