Geodesic
Reducing Off-Line to On-Line: an Example and Its Applications
Yugoslav journal of operations research, Tome 13 (2003) no. 1, p. 3 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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 [3], 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 - colorable induced subgraph of a given graph. For this problem we point out that, contrary to the first case, the on-line version is almost as well approximated as the off- line one.
Classification : 68R10 90C27
Keywords: Combinatorial problems, on-line computation, reductions, hereditary subgraph 
@article{YJOR_2003_13_1_a0,
     author = {Marc Demange},
     title = {Reducing {Off-Line} to {On-Line:} an {Example} and {Its} {Applications}},
     journal = {Yugoslav journal of operations research},
     pages = {3 },
     year = {2003},
     volume = {13},
     number = {1},
     zbl = {1054.68099},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2003_13_1_a0/}
}
TY  - JOUR
AU  - Marc Demange
TI  - Reducing Off-Line to On-Line: an Example and Its Applications
JO  - Yugoslav journal of operations research
PY  - 2003
SP  - 3 
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/YJOR_2003_13_1_a0/
LA  - en
ID  - YJOR_2003_13_1_a0
ER  - 
%0 Journal Article
%A Marc Demange
%T Reducing Off-Line to On-Line: an Example and Its Applications
%J Yugoslav journal of operations research
%D 2003
%P 3 
%V 13
%N 1
%U http://geodesic.mathdoc.fr/item/YJOR_2003_13_1_a0/
%G en
%F YJOR_2003_13_1_a0
Marc Demange. Reducing Off-Line to On-Line: an Example and Its Applications. Yugoslav journal of operations research, Tome 13 (2003) no. 1, p. 3 . http://geodesic.mathdoc.fr/item/YJOR_2003_13_1_a0/