Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872164 | Discrete Applied Mathematics | 2014 | 12 Pages |
Abstract
3. We also consider two geometrically defined hypergraphs. The first one is defined by subsets of a given set of n points in the Euclidean plane that are induced by half-planes. The second hypergraph is defined by subsets of a given set of n points in the plane induced by unit discs. For these hypergraphs, the competitive ratio obtained by Alon et al. is O(log2n). For both cases, we introduce an algorithm with O(logn)-competitive ratio. We also show that any online algorithm for both settings has a competitive ratio of Ω(logn), and hence our algorithms are optimal.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Guy Even, Shakhar Smorodinsky,