Thesis supervisor: György Dósa
Location of studies (in Hungarian): University of Pannonia, Faculty of Information Technology, Department of Mathematics Abbreviation of location of studies: PE
Description of the research topic:
Bin Packing is about 40 years old, as an independent discipline. Scheduling is a bit older. The whole theory of approximation algorithms and their efficiency estimates has been employed within these two disciplines. Many and significant articles are published in these areas.
Both areas are strongly related to the practice of industrial applications. Some tasks and algorithms are now considered classical, and appropriate modifications of these algorithms are often applied to solve new problems. These both topics are related to many other fields of science, for example graph theory, game theory; therefore, the subject is extremely diverse.
In the considered algorithms there are the so-called exact algorithms, approximation algorithms, heuristic methods, meta-heuristic methods. The investigation of these models can be interesting also from theoretical point of view, and also by computer experiments.
The task of the PhD student is the following: Investigation of certain areas within scheduling and/or bin packing, learning the existing results, gaining new, theoretic or experimental results regarding the investigated topic, publicate the results.
Preliminary results can be found in the following publications:
J. Balogh, J. Békési, G. Dosa, J. Sgall, R. van Stee, The optimal absolute ratio for online bin packing, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Diego, 2015 (January), pp. 1425-1438
J. Balogh, J. Bekesi, G. Dosa, L. Epstein, H. Kellerer, Zs. Tuza, Online Results for Black and White Bin Packing, Theory of Computing Systems, 2015, Vol 56, Iss 1, 137-155.
G. Dosa, First Fit Algorithm for Bin Packing, Reference Work Entry, Encyclopedia of Algorithms, 1-5, 12 November 2014
G. Dosa, Z. Tan, Zs. Tuza, Y. Yan, C. Sik Lányi, Improved Bounds for Batch Scheduling with Non-identical Job Sizes, Naval Research Logistics, 61(5), 351–358, 2014.
G. Dosa, L. Epstein, Preemptive scheduling on a small number of hierarchical machines, Information and Computation, 206 (5), 602-619, 2008.
Login
