Resumen de Intractable problems in novelty and diversity

Simone Santini , Pablo Castells Azpilicueta

• Information retrieval’s basic problem is retrieving a set of documents relevant for a given query. Here, we present three classes of methods that appeared in the literature, as well as a new one, which is an improvement of the one the three, to retrieve result sets that, in addition to relevance, try to maximize diversity and novelty. We analyze the complexity of these problems and show that whenever relevance, diversity, and novelty are considered together, the methods are all NP-complete.