Optimal Index Codes With Near-Extreme Rates
From MaRDI portal
Abstract: The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. Additionally, a new upper bound on the min-rank of a digraph, the circuit-packing bound, is presented. This bound is often tighter than the previously known bounds. By employing this new bound, we present several families of digraphs whose min-ranks can be found in polynomial time.
Recommendations
- A Rate–Distortion Approach to Index Coding
- Nonlinear Index Coding Outperforming the Linear Optimum
- Searching for (near) optimal codes
- Exact Random Coding Error Exponents of Optimal Bin Index Decoding
- Duality Codes and the Integrality Gap Bound for Index Coding
- Optimal Finite-Length and Asymptotic Index Codes for Five or Fewer Receivers
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- Capacity Theorems for Distributed Index Coding
- scientific article; zbMATH DE number 2036351
- Computing and Combinatorics
Cited in
(5)
This page was built for publication: Optimal Index Codes With Near-Extreme Rates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986475)
