Catalogo dei prodotti della ricerca

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. Copyright © by SIAM.

Finding the Jaccard median / Chierichetti, Flavio; R., Kumar; Sandeep, Pandey; Sergei, Vassilvitskii. - (2010), pp. 293-311. (Intervento presentato al convegno 21st ACM-SIAM Symposium on Discrete Algorithms, SODA 010 tenutosi a Austin, Texas, USA nel January 17-19, 2010).

Finding the Jaccard median

CHIERICHETTI, FLAVIO;
2010

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. Copyright © by SIAM.
2010
21st ACM-SIAM Symposium on Discrete Algorithms, SODA 010
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Finding the Jaccard median / Chierichetti, Flavio; R., Kumar; Sandeep, Pandey; Sergei, Vassilvitskii. - (2010), pp. 293-311. (Intervento presentato al convegno 21st ACM-SIAM Symposium on Discrete Algorithms, SODA 010 tenutosi a Austin, Texas, USA nel January 17-19, 2010).
04b Atto di convegno in volume
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/497799
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 61
  • ???jsp.display-item.citation.isi??? 38
social impact