Online algorithms for conversion problems: A survey

• We provide a classification scheme to unify the terminology and the notation of online conversion problems.
• Based on the factors (nature of search || nature of conversion || given information) we classify existing work.
• We analytically show how heuristic conversion algorithms can be evaluated using competitive analysis.
• Our scheme allows to evaluate the algorithms on existing methods and to compare them on a mutual basis.
• We highlight a number of questions that are still unanswered and require further consideration.

This paper surveys the literature devoted to online algorithms for conversion problems. We attempt to unify the terminology and the notation, while introducing the existing results based on a detailed problem classification. Algorithms on hand are reviewed based on our proposed scheme nature of search  ||nature of conversion  ||given information. We conclude that by the parameter given information existing algorithms as well as open problems can easily be identified.