Name
Abstract | ||
|---|---|---|
Index coding, a source coding problem over 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 information, corresponding to certain symbols of the input $textbf{x}$, which we represent as the information $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 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 rate. First, extending earlier work on planar graphs, we focus on approximating the 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 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/TIT.2019.2912184 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
Indexes,Servers,Network coding,Linear programming,Source coding,Approximation algorithms | Discrete mathematics,Broadcasting,Vertex (geometry),Source code,Symbol,Approximations of π,Coding (social sciences),Linear programming,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
abs/1807.07193 | 9 | 0018-9448 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhishek Agarwal | 1 | 8 | 1.53 |
| Larkin Flodin | 2 | 0 | 1.35 |
| Arya Mazumdar | 3 | 307 | 41.81 |