Linear Programming Approximations for Index Coding
- 22 April 2019
- journal article
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (9) , 5547-5564
Abstract
Index coding, a source coding problem over broadcast channels, has been a subject of both theoretical and practical interests since its introduction (by Birk and Kol, 1998). In short, the problem can be defined as follows: there is an input P (p 1 , ⋯ ,p n ), a set of n clients who each desire a single entry pi 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 entry. Additionally, each client has some predetermined “side information,” corresponding to the certain entries of the input P, which we represent as the “side information graph” G. The graph G has a vertex v i for client i and a directed edge (v i , v j ), indicating that client i knows the jth entry of the input. Given a fixed side information graph G, we are interested in determining or approximating the “broadcast rate” of index coding on the graph, i.e., the least number of messages the broadcaster can transmit so that every client recovers its desired information. The complexity of determining this broadcast rate in the most general case is open, and the best-known approximations are barely better than the trivial O(n)-approximation corresponding to sending each client their information directly without performing any coding. 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 the 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 best-known schemes. These can be viewed as both a strengthening of the constant-factor approximations proven for special graph families (as these schemes strictly improve on those which we prove are good approximations), as well as another tool that can be used either in practice or in future theoretical analyses.Keywords
All Related Versions
Funding Information
- Division of Computing and Communication Foundations (CCF 1642658)
- Division of Computing and Communication Foundations (CCF 1618512)
This publication has 26 references indexed in Scilit:
- Storage Capacity of Repairable NetworksIEEE Transactions on Information Theory, 2015
- Local time sharing for index coding2014
- Graph theory versus minimum rank for index coding2014
- Linear Index Coding via Semidefinite ProgrammingCombinatorics, Probability and Computing, 2013
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphsTheoretical Computer Science, 2007
- Informed-source coding-on-demand (ISCOD) over broadcast channels2002
- On the Hardness of Approximating the Chromatic NumberCombinatorica, 2000
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric GraphsJournal of Algorithms, 1998
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- Vertex packings: Structural properties and algorithmsMathematical Programming, 1975