On the Load Balancing Problem

Jul 7, 2017, 9:00 AM
30m

Speaker

Prof. Gabriel Semanišin (Faculty of Science, P.J. Šafárik University Košice, Slovakia)

Description

We present new results on the Load Balancing Problem that concerns and assigment of given jobs to a set of machines each of which can process a subset of jobs. Each job requires one unit of processing time and must be assigned to some machine that can process it. The jobs have to be assigned in such a manner that minimises the total completion time. We exploit graph theory models and the divide-and-conquer nature of the semi-matching problem. We derive three algorithms for the optimal semi-matching problem. The first one runs in time O(√n · m · log n) on a graph with n vertices and m edges. The second one is randomized and computes an optimal semi-matching with high probability in time O(n^c · log^(1+o(1)) n), where c is the exponent of the best known matrix multiplication algorithm. Since < 2.38, this algorithm breaks through O(n^2.5) barrier for dense graphs. In the case of planar graphs, the third one computes an optimal semi-matching in deterministic time O(n · log^4 n). The character of designed algorithms allows parallelisation and distributed computing.

Primary author

Prof. Gabriel Semanišin (Faculty of Science, P.J. Šafárik University Košice, Slovakia)

Co-authors

Dr František Galčík (Institute of Computer Science, Faculty of Science, P.J. Šafárik University, Košice, Slovakia) Dr Ján Katrenič (Institute of Computer Science, Faculty of Science, P.J. Šafárik University, Košice, Slovakia)

Presentation materials