Greedy Algorithms For On-Line Set-Covering

Authors

  • Giorgio Ausiello Dipartimento di Informatica e Sistemistica, Università degli Studi di Roma ``La Sapienza''
  • Nicolas Bourgeois LAMSADE, Université Paris-Dauphine
  • Telis Giannakos LAMSADE, Université Paris-Dauphine
  • Vangelis Th. Paschos LAMSADE, Université Paris-Dauphine

Keywords:

On-line algorithm, Approximation algorithm, Competitive ratio, Set-covering, Approximation ratio

Abstract

We study on-line models for the set-covering problem in which items from a ground set arrive one by one and with any such item c, the list of names of sets that contain it in the final instance is also presented possibly together with some information regarding the content of such sets. A decision maker has to select which set, among the sets containing c, has to be put in the solution in order to cover the item. Such decision has to be taken before a new item arrives and is irrevocable. The problem consists in minimizing the number of chosen sets. We first analyze some simple heuristics for the model in which only names of sets are provided. Then we show non trivial matching upper and lower bounds for the competitive ratio in the model in which for any item that arrives the content of all sets containing it is also revealed.

Downloads

Published

2009-02-03

How to Cite

Ausiello, G., Bourgeois, N., Giannakos, T., & Paschos, V. T. (2009). Greedy Algorithms For On-Line Set-Covering. Algorithmic Operations Research, 4(1), Pages 36 – 48. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/5928

Issue

Vol. 4 No. 1 (2009)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.