Towards Better Online Algorithms

This project will be concerned with examining some of the most important on-line problems and analyzing them using the relative worst order ratio in order to develop new algorithms that in practice outperforms existing algorithms, that was developed with the competitive ratio in mind.

The work will be initiated with a study of the literature on existing algorithms for paging, bin packing and similar fundamental on-line problems. This will be followed up by a combination of algorithm design, algorithm analysis, and experimental work. It is the hope that the project will result in a number of improved algorithms, as described above, and as a result a greater insight into effective algorithms for problems of this kind.