Finding the Jaccard Median

Flavio Chierichetti, Ravi Kumar, Sandeep Pandey, Sergei Vassilvitskii

Abstract

The median problem in the weighted Jaccard metric was analyzed by Späth in 1981. Up until now, only an exponential-time exact algorithm was known. We (a) obtain a PTAS for the weighted Jaccard median problem and (b) show that the problem does not admit a FPTAS (assuming P ≠ NP), even when restricted to binary vectors. The PTAS is built on a number of different algorithmic ideas and the hardness result makes use of an especially interesting gadget.
BibTeX
@inproceedings{chierichetti2010finding,
  author = {Flavio Chierichetti and Ravi Kumar and Sandeep Pandey and Sergei Vassilvitskii},
  title = {{Finding the Jaccard Median}},
  booktitle = {SODA},
  year = {2010},
  doi = {10.1137/1.9781611973075.25},
}

Loading related content...

Figure