Responsible instructor: György Dósa, DSc (dosa.gyorgy@mik.uni-pannon.hu)
Thematics:
Scheduling
Scheduling models, approximation algorithms, efficiency estimations
Approximation schemes
Online scheduling. Lower bound constructions, algorithms, competitive ratio
Semi-online scheduling, main models, results
Bin Packing
The classical Bin Packing Problem
"Fit" algorithms: Next Fit, First Fit, Best Fit, Worst Fit, Any Fit, Almost Any Fit
Weight function technique
Approximation schemes
Online BP, lower and upper bounds (Harmonic-Fit type algorithms)
Rectangle packing, vector packing, other models
Literature:
Chen B., Potts C. N., Woeginger G. A review of machine scheduling: Complexity, algorithms and approximability. In Du D.-Z. and Pardalos P. M. (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 1998.
Sgall, J. On-line scheduling, in: On-line Algorithms: The State of Art, Lecture Notes in Computer Science 1442, Springer-Verlag, 196–231, 1998.
Tan Zhiyi, Zhang An, Online and Semi-online Scheduling, In: Pardalos Panos M, Du Ding-Zhu, Graham Ronald L (szerk.) : Handbook of Combinatorial Optimization. Springer New York, 2013. pp. 2191-2252.
Coffman E. G. Jr., Garey M. R., Johnson D. S. Approximation algorithms for bin packing: a survey, in: Hochbaum D. (ed.), Approximation algorithms. PWS Publ. Co., 1997.
Coffman E. G Jr., Csirik J., Galambos G., Martello S., Vigo D., Bin Packing Approximation Algorithms: Survey and Classification. In: Handbook of Combinatorial Optimization. Springer New York, 2013. pp. 455-531.