Back to Search
Start Over
Polynomial Time Approximation Schemes for All 1-Center Problems on Metric Rational Set Similarities.
- Source :
-
Algorithmica . May2021, Vol. 83 Issue 5, p1371-1392. 22p. - Publication Year :
- 2021
-
Abstract
- In this paper, we investigate algorithms for finding centers of a given collection N of sets. In particular, we focus on metric rational set similarities, a broad class of similarity measures including Jaccard and Hamming. A rational set similarity S is called metric if D = 1 - S is a distance function. We study the 1-center problem on these metric spaces. The problem consists of finding a set C that minimizes the maximum distance of C to any set of N . We present a general framework that computes a (1 + ε) approximation for any metric rational set similarity. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 83
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 149714885
- Full Text :
- https://doi.org/10.1007/s00453-020-00787-3