Papers › Sequential Diversification with Provable Guarantees
Sequential Diversification with Provable Guarantees
Honglian Wang, Sijing Tu, Aristides Gionis
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Diversification is a useful tool for exploring large collections of information items. It has been used to reduce redundancy and cover multiple perspectives in information-search settings. Diversification finds applications in many different domains, including presenting search results of information-retrieval systems and selecting suggestions for recommender systems. Interestingly, existing measures of diversity are defined over \emph{sets} of items, rather than evaluating \emph{sequences} of items. This design choice comes in contrast with commonly-used relevance measures, which are distinctly defined over sequences of items, taking into account the ranking of items. The importance of employing sequential measures is that information items are almost always presented in a sequential manner, and during their information-exploration activity users tend to prioritize items with higher~ranking. In this paper, we study the problem of \emph{maximizing sequential diversity}. This is a new measure of \emph{diversity}, which accounts for the \emph{ranking} of the items, and incorporates \emph{item relevance} and \emph{user behavior}. The overarching framework can be instantiated with different diversity measures, and here we consider the measures of \emph{sum~diversity} and \emph{coverage~diversity}. The problem was recently proposed by Coppolillo et al.~\citep{coppolillo2024relevance}, where they introduce empirical methods that work well in practice. Our paper is a theoretical treatment of the problem: we establish the problem hardness and present algorithms with constant approximation guarantees for both diversity measures we consider. Experimentally, we demonstrate that our methods are competitive against strong baselines.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections