Linear Index Coding via Semidefinite Programming
From MaRDI portal
Publication:5410256
DOI10.1017/S0963548313000564zbMath1287.94024arXiv1107.1958MaRDI QIDQ5410256
Publication date: 16 April 2014
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.1958
Semidefinite programming (90C22) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Information theory (general) (94A15)
Related Items
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank, Unnamed Item, Unnamed Item, Unnamed Item, The minrank of random graphs, Unnamed Item, Topological bounds on the dimension of orthogonal representations of graphs
Cites Work
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Orthogonal representations over finite fields and the chromatic number of graphs
- Conditional Hardness for Approximate Coloring
- Improving the performance guarantee for approximate graph coloring
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
- New approximation algorithms for graph coloring
- Network information flow
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Distributed source coding for satellite communications
- Coloring -colorable graphs using relatively small palettes
- Nonlinear Index Coding Outperforming the Linear Optimum
- Index Coding With Side Information
- On the Hardness of Approximating the Network Coding Capacity
- On the hardness of approximating the chromatic number
