Pliable Index Coding via Conflict-Free Colorings of Hypergraphs
From MaRDI portal
Abstract: In the pliable index coding (PICOD) problem, a server is to serve multiple clients, each of which possesses a unique subset of the complete message set as side information and requests a new message which it does not have. The goal of the server is to do this using as few transmissions as possible. This work presents a hypergraph coloring approach to the scalar PICOD problem. A extit{conflict-free coloring} of a hypergraph is known from literature as an assignment of colors to its vertices so that each hyperedge of the graph contains one uniquely colored vertex. For a given PICOD problem represented by a hypergraph consisting of messages as vertices and request-sets as hyperedges, we present achievable PICOD schemes using conflict-free colorings of the PICOD hypergraph. Various graph theoretic parameters arising out of such colorings (and some new coloring variants) then give a number of upper bounds on the optimal PICOD length, which we study in this work. Suppose the PICOD hypergraph has vertices and hyperedges, where every hyperedge overlaps with at most other hyperedges. We show easy to implement randomized algorithms for the following: (a) For the single request case, we give a PICOD of length . This result improves over known achievability results for some parameter ranges, (b) For the -request case, we give an MDS code of length . Further if the hyperedges (request sets) are sufficiently large, we give a PICOD of the same length as above, which is not based on MDS construction. In general, this gives an improvement over prior achievability results. Our codes are of near-optimal length (up to a multiplicative factor of ).
This page was built for publication: Pliable Index Coding via Conflict-Free Colorings of Hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6359757)
