In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially present (in our case the complete graph on the order of the final graph) and edges are progressively removed until the achievement of the final graph. Next, we revisit the model introduced in [Demange, Paradon and Paschos, Lect. Notes Comput. Sci. 1963 (2000) 326-334] and study relaxations assuming that some paying backtracking is allowed.
Mots-clés : approximation algorithms, competitive ratio, maximum independent set, on-line algorithms
@article{RO_2006__40_2_129_0,
author = {Escoffier, Bruno and Paschos, Vangelis Th.},
title = {On-line models and algorithms for max independent set},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {129--142},
publisher = {EDP-Sciences},
volume = {40},
number = {2},
year = {2006},
doi = {10.1051/ro:2006014},
mrnumber = {2272683},
zbl = {1110.68170},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro:2006014/}
}
TY - JOUR AU - Escoffier, Bruno AU - Paschos, Vangelis Th. TI - On-line models and algorithms for max independent set JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 129 EP - 142 VL - 40 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2006014/ DO - 10.1051/ro:2006014 LA - en ID - RO_2006__40_2_129_0 ER -
%0 Journal Article %A Escoffier, Bruno %A Paschos, Vangelis Th. %T On-line models and algorithms for max independent set %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 129-142 %V 40 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2006014/ %R 10.1051/ro:2006014 %G en %F RO_2006__40_2_129_0
Escoffier, Bruno; Paschos, Vangelis Th. On-line models and algorithms for max independent set. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 2, pp. 129-142. doi : 10.1051/ro:2006014. http://archive.numdam.org/articles/10.1051/ro:2006014/
[1] ,,, and, Algorithms for the on-line traveling salesman problem. Algorithmica 29 (2001) 560-581. | Zbl
[2] , Graphs and hypergraphs. North Holland, Amsterdam (1973). | MR | Zbl
[3] , and, On-line maximum-order induced hereditary subgraph problems, in SOFSEM 2000-Theory and Practice of Informatics, edited by V. Hlaváč, K.G. Jeffery and J. Wiedermann. Springer-Verlag, Lect. Notes Comput. Sci. 1963 (2000) 326-334. | Zbl
[4] ,, Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett. 10 (1997) 105-110. | Zbl
[5] ,, Improved approximations for weighted and unweighted graph problems. Theor. Comput. Syst. To appear. | MR | Zbl
[6] , Problème on-line du stable de cardinalité maximale. Mémoire de DEA (2002).
[7] , Approximations via partitioning. JAIST Research Report IS-RR-95-0003F, Japan Advanced Institute of Science and Technology, Japan (1995).
[8] , Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appli. 4 (2000) 1-16. | Zbl
[9] ,, and, Online independent sets. Theoret. Comput. Sci. 289 (2002) 953-962. | Zbl
[10] , editor, Approximation algorithms for NP-hard problems. PWS, Boston (1997).
[11] , A survey about how optimal solutions to some covering and packing problems can be approximated. ACM Comput. Surveys 29 (1997) 171-209.
Cité par Sources :
