Finding the Jaccard Median
Lists
Only you see this
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...