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 Network Coding Capacity
- On the Shannon capacity of a graph
- On the hardness of approximating the chromatic number
- Orthogonal representations over finite fields and the chromatic number of graphs
Cited in
(14)- A bound on the Shannon capacity via a linear programming variation
- Approximating the orthogonality dimension of graphs and hypergraphs
- scientific article; zbMATH DE number 7561683 (Why is no real title available?)
- On minrank and forbidden subgraphs
- A Linear Encoding Approach to Index Assignment in Lossy Source-Channel Coding
- Linear index coding via semidefinite programming
- Polynomial time algorithm for min-ranks of graphs with simple tree structures
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- Fundamentals of index coding
- A Polynomial-Time Algorithm for Pliable Index Coding
- On minrank and the Lovász theta-function
- Topological bounds on the dimension of orthogonal representations of graphs
- The minrank of random graphs
- Linear Programming Approximations for Index Coding
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)
