Linear Programming Approximations for Index Coding

DOI10.1109/TIT.2019.2912184MaRDI QIDQ5211387zbMATH OpenOpenAlexWikidataFDO

Authors Abhishek Agarwal, Larkin Flodin, Arya Mazumdar

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.07193

zbMATH Keywords

index codingsource coding problem over broadcast channels

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Source coding (94A29)

Abstract: 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 $extbfxriangleq(extbf{x}_1,dots,extbf{x}_n)$, a set of $n$ clients who each desire a single symbol $extbf{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 $extbfx$, which we represent as the "side information graph" $mathcalG$. The graph $mathcalG$ 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 $mathcalG$, 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.

Recommendations

• Linear index coding via semidefinite programming
• Linear index coding via semidefinite programming
• A Linear Encoding Approach to Index Assignment in Lossy Source-Channel Coding
• The linear programming bound for binary linear codes
• Decoding low-dimensional linear codes by linear programming
• Linear programming bounds for codes via a covering argument
• A Polynomial-Time Algorithm for Pliable Index Coding
• Nonlinear Index Coding Outperforming the Linear Optimum
• Linear programming bounds for codes of small size
• Efficient Implementation of Linear Programming Decoding

Cited in

(4)

• A Polynomial-Time Algorithm for Pliable Index Coding
• A Linear Encoding Approach to Index Assignment in Lossy Source-Channel Coding
• scientific article; zbMATH DE number 7536575 (Why is no real title available?)
• Kernels for storage capacity and dual index coding

This page was built for publication: Linear Programming Approximations for Index Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211387)