On-line models and algorithms for max independent set

Bruno Escoffier; Vangelis Th. Paschos

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 2, page 129-142
  • ISSN: 0399-0559

Abstract

top
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 n 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.

How to cite

top

Escoffier, Bruno, and Paschos, Vangelis Th.. "On-line models and algorithms for max independent set." RAIRO - Operations Research 40.2 (2006): 129-142. <http://eudml.org/doc/249628>.

@article{Escoffier2006,
abstract = { 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 n 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. },
author = {Escoffier, Bruno, Paschos, Vangelis Th.},
journal = {RAIRO - Operations Research},
keywords = {Approximation algorithms; competitive ratio; maximum independent set; on-line algorithms.; approximation algorithms; maximum independent set; on-line algorithms},
language = {eng},
month = {10},
number = {2},
pages = {129-142},
publisher = {EDP Sciences},
title = {On-line models and algorithms for max independent set},
url = {http://eudml.org/doc/249628},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Escoffier, Bruno
AU - Paschos, Vangelis Th.
TI - On-line models and algorithms for max independent set
JO - RAIRO - Operations Research
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 2
SP - 129
EP - 142
AB - 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 n 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.
LA - eng
KW - Approximation algorithms; competitive ratio; maximum independent set; on-line algorithms.; approximation algorithms; maximum independent set; on-line algorithms
UR - http://eudml.org/doc/249628
ER -

References

top
  1. G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie and M. Talamo, Algorithms for the on-line traveling salesman problem. Algorithmica29 (2001) 560–581.  
  2. C. Berge, Graphs and hypergraphs. North Holland, Amsterdam (1973).  
  3. M. Demange, X. Paradon and V.Th. Paschos, 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.  
  4. M. Demange, V.Th. Paschos, Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett.10 (1997) 105–110.  
  5. M. Demange, V.Th. Paschos, Improved approximations for weighted and unweighted graph problems. Theor. Comput. Syst. To appear.  
  6. B. Escoffier, Problème on-line du stable de cardinalité maximale. Mémoire de DEA (2002).  
  7. M.M. Halldórsson, Approximations via partitioning. JAIST Research Report IS-RR-95-0003F, Japan Advanced Institute of Science and Technology, Japan (1995).  
  8. M.M. Halldórsson, Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appli.4 (2000) 1–16.  
  9. M.M. Halldórsson, K. Iwama, S. Miyazaki and S. Taketomi, Online independent sets. Theoret. Comput. Sci.289 (2002) 953–962.  
  10. D.S. Hochbaum, editor, Approximation algorithms for NP-hard problems. PWS, Boston (1997).  
  11. V.Th. Paschos, A survey about how optimal solutions to some covering and packing problems can be approximated. ACM Comput. Surveys29 (1997) 171–209.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.