  Social media have a great potential to improve information dissemination in
our society, yet, they have been held accountable for a number of undesirable
effects, such as polarization and filter bubbles. It is thus important to
understand these negative phenomena and develop methods to combat them. In this
paper we propose a novel approach to address the problem of breaking filter
bubbles in social media. We do so by aiming to maximize the diversity of the
information exposed to connected social-media users. We formulate the problem
of maximizing the diversity of exposure as a quadratic-knapsack problem. We
show that the proposed diversity-maximization problem is inapproximable, and
thus, we resort to polynomial non-approximable algorithms, inspired by
solutions developed for the quadratic-knapsack problem, as well as scalable
greedy heuristics. We complement our algorithms with instance-specific upper
bounds, which are used to provide empirical approximation guarantees for the
given problem instances. Our experimental evaluation shows that a proposed
greedy algorithm followed by randomized local search is the algorithm of choice
given its quality-vs.-efficiency trade-off.
