Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Approximately Dominating Representatives
verfasst von : Vladlen Koltun, Christos H. Papadimitriou
Erschienen in: Database Theory - ICDT 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose and investigate from the algorithmic standpoint a novel form of fuzzy query called
approximately dominating representatives
or ADRs. The ADRs of a multidimensional point set consist of a few points guaranteed to contain an approximate optimum of
any
monotone Lipschitz continuous combining function of the dimensions. ADRs can be computed by appropriately post-processing Pareto, or “skyline,” queries [14,1]. We show that the problem of minimizing the number of points returned, for a user-specified desired approximation, can be solved in polynomial time in two dimensions; for three and more it is NP-hard but has a polynomial-time logarithmic approximation. Finally, we present a polynomial-time, constant factor approximation algorithm for three dimensions.