Name
Abstract | ||
|---|---|---|
We study the following on-line model for set-covering: elements of a ground set of size n arrive one-by-one and with any such element ci, arrives also the name of some set Si0 containing ci and covering the most of the uncovered ground set- elements (obviously, these elements have not been yet revealed). For this model we analyze a simple greedy algorithm consisting of taking Si0 into the cover, only if ci is not already covered. We prove that the competitive ratio of this algorithm, that uses only O(logm) space, where m is the size of the set-system, is √ n and that it is asymptotically optimal for the model dealt, since no on-line algorithm can do better than n/2. We next show that this model can also be used for solving minimum dominating set with competitive ratio bounded above by the square root of the size of the input graph. We also study a slightly simplified, but more memory consum- ing, on-line model: any time a ground set-element arrives, the whole sequence of the names of the sets containing it is revealed. For this model, we propose an algo- rithm achieving competitive ratio bounded above by the maximum frequency of the instance, i.e., by the maximum number of sets containing a ground set-element. We finally deal with the maximum budget saving problem. Here, an initial budget is al- lotted that is destined to cover the cost of an algorithm for solving set-covering. The objective is to maximize the savings on the initial budget. We show that when this budget is at least equal to √ n times the size of the optimal (off-line) solution of the instance under consideration, then the natural greedy off-line algorithm is asymptot- ically optimal. |
Year | Venue | Keywords |
|---|---|---|
2009 | Algorithmic Operations Research | competitive ratio,approximation algorithm,set cover,greedy algorithm |
Field | DocType | Volume |
Approximation algorithm,Mathematical optimization,Combinatorics,Upper and lower bounds,Greedy algorithm,Heuristics,Mathematics,Decision maker,Competitive analysis | Journal | 4 |
Issue | Citations | PageRank |
1 | 2 | 0.40 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Giorgio Ausiello | 1 | 863 | 408.95 |
| Nicolas Bourgeois | 2 | 99 | 7.96 |
| Telis Giannakos | 3 | 2 | 0.40 |
| Vangelis Th. Paschos | 4 | 633 | 63.97 |