  Index coding, a source coding problem over broadcast channels, has been a
subject of both theoretical and practical interest since its introduction (by
Birk and Kol, 1998). In short, the problem can be defined as follows: there is
an input $\textbf{x} \triangleq (\textbf{x}_1, \dots, \textbf{x}_n)$, a set of
$n$ clients who each desire a single symbol $\textbf{x}_i$ of the input, and a
broadcaster whose goal is to send as few messages as possible to all clients so
that each one can recover its desired symbol. Additionally, each client has
some predetermined "side information," corresponding to certain symbols of the
input $\textbf{x}$, which we represent as the "side information graph"
$\mathcal{G}$. The graph $\mathcal{G}$ has a vertex $v_i$ for each client and a
directed edge $(v_i, v_j)$ indicating that client $i$ knows the $j$th symbol of
the input. Given a fixed side information graph $\mathcal{G}$, we are
interested in determining or approximating the "broadcast rate" of index coding
on the graph, i.e. the fewest number of messages the broadcaster can transmit
so that every client gets their desired information.
  Using index coding schemes based on linear programs (LPs), we take a
two-pronged approach to approximating the broadcast rate. First, extending
earlier work on planar graphs, we focus on approximating the broadcast rate for
special graph families such as graphs with small chromatic number and disk
graphs. In certain cases, we are able to show that simple LP-based schemes give
constant-factor approximations of the broadcast rate, which seem extremely
difficult to obtain in the general case. Second, we provide several LP-based
schemes for the general case which are not constant-factor approximations, but
which strictly improve on the prior best-known schemes.
