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 assignment 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
Frantisek Galčík
(Institute of Computer Science, Faculty of Science, P.J. Šafárik University in Košice, Košice, Slovakia)
Dr
J. Katrenič
(Institute of Computer Science, Faculty of Science, P.J. Šafárik University in Košice, Košice, Slovakia)
