  Given a graph $G = (V, E)$ and a model of information flow on that network, a
fundamental question is to understand if all the nodes have sufficient access
to information generated at other nodes in the graph. If not, we can ask if a
small set of edge additions improve information access. Formally, the broadcast
value of a network is defined to be the minimum over pairs $u,v \in V$ of the
probability that an information cascade starting at $u$ reaches $v$. Recent
work in the algorithmic fairness literature has focused on heuristics for
adding a few edges to a graph to improve its broadcast. Our goal is to formally
study the approximability of the Broadcast Improvement problem: given $G$ and a
parameter $k$, find the best set of $k$ edges to add to $G$ in order to
maximize the broadcast value of the resulting graph.
  We develop efficient bicriteria approximation algorithms. If the optimal
solution adds $k$ edges and achieves a broadcast of $\beta^*$, we develop
algorithms that can (a) add $2k-1$ edges and achieve a broadcast value roughly
$(\beta^*)^4$, or (b) add $O(k\log n)$ edges and achieve a broadcast roughly
$\beta^*$. We also provide other trade-offs, that can be better depending on
$k$ and the parameter associated with propagation in the cascade model. We
complement our results by proving that unless P = NP, any algorithm that adds
$O(k)$ edges must lose significantly in the approximation of $\beta^*$,
resolving an open question.
  Our techniques are inspired by connections between Broadcast Improvement and
problems such as Metric $k$-Center and Diameter Reduction. However, since the
objective involves information cascades, we need to develop novel probabilistic
tools to reason about the existence of paths in edge-sampled graphs. Finally,
we show that our techniques extend to a single-source variant, for which we
show both bicriteria algorithms and inapproximability results.
