TY - JOUR
AU - Giorgio Ausiello
AU - Nicolas Bourgeois
AU - Telis Giannakos
AU - Vangelis Th. Paschos
PY - 2009/02/03
Y2 - 2019/10/18
TI - Greedy Algorithms For On-Line Set-Covering
JF - Algorithmic Operations Research
JA - AOR
VL - 4
IS - 1
SE - Articles
DO -
UR - https://journals.lib.unb.ca/index.php/AOR/article/view/5928
AB - 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.
ER -