Authors
Flavio Chierichetti, Ravi Kumar, Sandeep Pandey, Sergei Vassilvitskii
Publication date
2010/1/17
Conference
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms
Pages
293-311
Publisher
Society for Industrial and Applied Mathematics
Description
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.
Total citations
Scholar articles
F Chierichetti, R Kumar, S Pandey, S Vassilvitskii - Proceedings of the twenty-first annual ACM-SIAM …, 2010