Linear index coding via semidefinite programming
From MaRDI portal
Abstract: In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to broadcast an n bit word to n receivers (one bit per receiver), where the receivers have side information represented by a graph G. The objective is to minimize the length of a codeword sent to all receivers which allows each receiver to learn its bit. For linear index coding, the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef et al., FOCS, 2006). We show a polynomial time algorithm that, given an n vertex graph G with minrank k, finds a linear index code for G of length , where f(k) depends only on k. For example, for k=3 we obtain f(3) ~ 0.2574. Our algorithm employs a semidefinite program (SDP) introduced by Karger, Motwani and Sudan (J. ACM, 1998) for graph coloring and its refined analysis due to Arora, Chlamtac and Charikar (STOC, 2006). Since the SDP we use is not a relaxation of the minimization problem we consider, a crucial component of our analysis is an upper bound on the objective value of the SDP in terms of the minrank. At the heart of our analysis lies a combinatorial result which may be of independent interest. Namely, we show an exact expression for the maximum possible value of the Lovasz theta-function of a graph with minrank k. This yields a tight gap between two classical upper bounds on the Shannon capacity of a graph.
Recommendations
Cites work
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Approximate graph coloring by semidefinite programming
- Coloring -colorable graphs using relatively small palettes
- Conditional Hardness for Approximate Coloring
- Distributed source coding for satellite communications
- Improving the performance guarantee for approximate graph coloring
- Index Coding With Side Information
- Network information flow
- New approximation algorithms for graph coloring
- Nonlinear Index Coding Outperforming the Linear Optimum
- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
- On the Hardness of 4-Coloring a 3-Colorable Graph
- On the hardness of approximating the chromatic number
- On the Hardness of Approximating the Network Coding Capacity
- On the Shannon capacity of a graph
- Orthogonal representations over finite fields and the chromatic number of graphs
Cited in
(14)- Polynomial time algorithm for min-ranks of graphs with simple tree structures
- Topological bounds on the dimension of orthogonal representations of graphs
- A Polynomial-Time Algorithm for Pliable Index Coding
- A bound on the Shannon capacity via a linear programming variation
- Fundamentals of index coding
- A Linear Encoding Approach to Index Assignment in Lossy Source-Channel Coding
- The minrank of random graphs
- On minrank and the Lovász theta-function
- On minrank and forbidden subgraphs
- Approximating the orthogonality dimension of graphs and hypergraphs
- Linear Programming Approximations for Index Coding
- Linear index coding via semidefinite programming
- Approximating the orthogonality dimension of graphs and hypergraphs
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
This page was built for publication: Linear index coding via semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5410256)
