Optimal index codes with near-extreme rates
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. Thos...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/102539 http://hdl.handle.net/10220/16391 |
| _version_ | 1811684021669724160 |
|---|---|
| author | Dau, Son Hoang Skachek, Vitaly Chee, Yeow Meng |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Dau, Son Hoang Skachek, Vitaly Chee, Yeow Meng |
| author_sort | Dau, Son Hoang |
| collection | NTU |
| description | 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. It is also shown that the decision problem of whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. |
| first_indexed | 2024-10-01T04:22:00Z |
| format | Conference Paper |
| id | ntu-10356/102539 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:22:00Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/1025392020-03-07T12:31:20Z Optimal index codes with near-extreme rates Dau, Son Hoang Skachek, Vitaly Chee, Yeow Meng School of Physical and Mathematical Sciences IEEE International Symposium on Information Theory (2012 : Cambridge, US) DRNTU::Science::Mathematics 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. It is also shown that the decision problem of whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. 2013-10-10T06:09:26Z 2019-12-06T20:56:44Z 2013-10-10T06:09:26Z 2019-12-06T20:56:44Z 2012 2012 Conference Paper Dau, S. H., Skachek, V., & Chee, Y. M. (2012). Optimal index codes with near-extreme rates. 2012 IEEE International Symposium on Information Theory - ISIT, pp.2241-2245. https://hdl.handle.net/10356/102539 http://hdl.handle.net/10220/16391 10.1109/ISIT.2012.6283852 en |
| spellingShingle | DRNTU::Science::Mathematics Dau, Son Hoang Skachek, Vitaly Chee, Yeow Meng Optimal index codes with near-extreme rates |
| title | Optimal index codes with near-extreme rates |
| title_full | Optimal index codes with near-extreme rates |
| title_fullStr | Optimal index codes with near-extreme rates |
| title_full_unstemmed | Optimal index codes with near-extreme rates |
| title_short | Optimal index codes with near-extreme rates |
| title_sort | optimal index codes with near extreme rates |
| topic | DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/102539 http://hdl.handle.net/10220/16391 |
| work_keys_str_mv | AT dausonhoang optimalindexcodeswithnearextremerates AT skachekvitaly optimalindexcodeswithnearextremerates AT cheeyeowmeng optimalindexcodeswithnearextremerates |