Article ID: | iaor20033285 |
Country: | Serbia |
Volume: | 13 |
Issue: | 1 |
Start Page Number: | 3 |
End Page Number: | 24 |
Publication Date: | Jan 2003 |
Journal: | Yugoslav Journal of Operations Research |
Authors: | Demange Marc |
Keywords: | computational analysis |
We study on-line versions of maximum weighted hereditary subgraph problems for which the instance is revealed in two clusters. We focus on the comparison of these on-line problems with their respective off-line versions. In an earlier paper we have reduced on-line versions to the off-line ones in order to devise competitive analysis for such problems. In this paper, we first devise hardness results pointing out that this previous analysis was tight. Then, we propose a process that allows, for a large class of hereditary problems, to transform an on-line algorithm into an off-line one with improvement of the guarantees. This result can be seen as an inverse version of our previous work. It brings to the fore a hardness gap between on-line and off-line versions of those problems. This result does not apply in the case of maximizing a