2026-07-22T09:18:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7376 2024-03-06T10:40:18Z ddc:004 open_access

On Finding the Jaccard Center Bury, Marc Schwiegelshohn, Chris Clustering 1-Center Jaccard We initiate the study of finding the Jaccard center of a given collection N of sets. For two sets X,Y, the Jaccard index is defined as |X\cap Y|/|X\cup Y| and the corresponding distance is 1-|X\cap Y|/|X\cup Y|. The Jaccard center is a set C minimizing the maximum distance to any set of N. We show that the problem is NP-hard to solve exactly, and that it admits a PTAS while no FPTAS can exist unless P = NP. Furthermore, we show that the problem is fixed parameter tractable in the maximum Hamming norm between Jaccard center and any input set. Our algorithms are based on a compression technique similar in spirit to coresets for the Euclidean 1-center problem. In addition, we also show that, contrary to the previously studied median problem by Chierichetti et al. (SODA 2010), the continuous version of the Jaccard center problem admits a simple polynomial time algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marc Bury and Chris Schwiegelshohn 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.23 urn:nbn:de:0030-drops-73769 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.23 eng https://creativecommons.org/licenses/by/3.0/legalcode