检索结果-内蒙古大学图书馆

Improved Approximation Algorithms for index coding

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第11期70卷 8266-8275页

作者： Chawin, Dror Haviv, Ishay Acad Coll Tel Aviv Yaffo Sch Comp Sci IL-61083 Tel Aviv Israel

The index coding problem is concerned with broadcasting encoded information to a collection of receivers in a way that enables each receiver to discover its required data based on its side information, which comprises the data required by some of the others. Given the side information map, represented by a graph in the symmetric case and by a digraph otherwise, the goal is to devise a coding scheme of minimum broadcast length. We present a general method for developing efficient algorithms for approximating the index coding rate for prescribed families of instances. As applications, we obtain polynomial-time algorithms that approximate the index coding rate of graphs and digraphs on n vertices to within factors of O(n/log(2)n) and O(n/log n) respectively. This improves on the approximation factors of O(n/log n) for graphs and O(n & sdot;log log n/log n) for digraphs achieved by Blasiak, Kleinberg, and Lubetzky. For the family of quasi-line graphs, we exhibit a polynomial-time algorithm that approximates the index coding rate to within a factor of 2. This improves on the approximation factor of O(n(2/3)) achieved by Arbabjolfaei and Kim for graphs on n vertices taken from certain sub-families of quasi-line graphs. Our approach is applicable for approximating a variety of additional graph and digraph quantities to within the same approximation factors. Specifically, it captures every graph quantity sandwiched between the independence number and the clique cover number and every digraph quantity sandwiched between the maximum size of an acyclic induced sub-digraph and the directed clique cover number.

关键词： approximation algorithms clique cover index coding approximation algorithms clique cover

来源：评论

学校读者我要写书评

暂无评论

On the index coding Problem and Its Relation to Network coding and Matroid Theory

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第7期56卷 3187-3195页

作者： El Rouayheb, Salim Sprintson, Alex Georghiades, Costas Texas A&M Univ Dept Elect & Comp Engn College Stn TX 77843 USA

The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages X = {x(1),...,x(k)} and a set of receivers R. Each receiver rho = (x,H) in R needs to obtain a message x is an element of X and has prior side information consisting of a subset H of X. The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.

关键词： index coding matroid theory network coding nonlinear codes side information

来源：评论

学校读者我要写书评

暂无评论

On the Optimal Broadcast Rate of the Two-Sender Unicast index coding Problem With Fully-Participated Interactions

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第12期67卷 8612-8623页

作者： Arunachala, Chinmayananda Aggarwal, Vaneet Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

The problem of two-sender unicast index coding consists of two senders and a set of receivers. Each receiver demands a unique message not demanded by any other receiver and has a subset of messages as its side information. Every demanded message is available with at least one of the senders. The senders avail the knowledge of the side information at all the receivers to reduce the total number of transmissions required to satisfy the demands of all the receivers. The objective is to find the minimum total of number of transmissions per message length (known as the optimal broadcast rate with finite length messages) and its limiting value as the message length tends to infinity (called the optimal broadcast rate). Achievable broadcast rates are provided for a class of the two-sender unicast index coding problem based on a special graph coloring technique called two-sender graph coloring. This result illustrates the utility of graph products in the two-sender unicast index coding problem for the first time in the literature. For another class, achievable broadcast rates are provided based on the optimal broadcast rates of three single-sender sub-problems with finite message length. This employs a code construction for the two-sender unicast index coding problem using optimal codes (including non-linear codes) of the sub-problems. Optimal broadcast rates are provided for a special class of the TUICP for which only an upper bound was known prior to this work. The optimal broadcast rates presented in this work also consider non-linear coding schemes at the two senders.

关键词： index coding side-information two-sender unicast index coding optimal broadcast rate

来源：评论

学校读者我要写书评

暂无评论

Pliable index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第11期61卷 6192-6203页

作者： Brahma, Siddhartha Fragouli, Christina Ecole Polytech Fed Lausanne Dept Comp & Commun Sci CH-1015 Lausanne Switzerland

We formulate a new variant of the index coding problem, where instead of demanding a specific message, clients are pliable, and are interested in receiving any t messages that they do not have. We term this problem pliable index coding or PICOD(t). We prove that, with this formulation, although some instances of the problem become simple, in general, the problem of finding the optimal linear code remains NP-hard. However, we show that it is possible to construct pliable index codes that are substantially smaller than index codes in many cases. If there are n clients, the server has m messages, and each client has a side information set of cardinality s <= m - t;we show that O(min{t log n, t + log(2) n}) broadcast transmissions are sufficient to satisfy all the clients. For t = 1, this is an exponential improvement over the n messages required in index coding in the worst case (for m = n). In addition, for t >> log(2) n, the number of broadcast transmissions required is only linearly dependent on t. We generalize the results to instances where the side information sets are not necessarily of equal cardinality. When m = O(n(delta)), for some constant delta > 0, we show that the codes of size O(min{t log(2) n, t log n + log(3) n}) are sufficient in general. We also consider the scenario when the server only knows the cardinality of the side information sets of the clients and each client is interested in receiving any t messages that it does not have. We term this formulation oblivious pliable index coding or OB-PICOD(t). If the cardinalities of side information sets of all the clients is s (with s <= m - t), then we show that min{s + t, m - s} messages are both sufficient and necessary for linear codes. Finally, we develop efficient heuristic approximation algorithms for PICOD(t) and show through simulations on the random instances of PICOD(t) that they perform well in practice.

关键词： index coding broadcast channel greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Capacity of Symmetric index coding Problems With X-Network Setting With 2 x 2 Local Connectivity

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2018年第3期7卷 396-399页

作者： Vaddi, Mahesh Babu Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India

In X-network setting with L x L local connectivity, we have a locally connected network where each receiver is connected to L consecutive base stations and each base station has a distinct message for each connected receiver. Maleki et al. modeled the X-network setting with L x L local connectivity as a multiple unicast index coding problem and proved that the capacity of symmetric index coding problems with locally connected X-network with K number of receivers and number of messages M = KL and K tending to infinity is (2/[L(L+1)]) and for finite number of receivers this was shown to be an upper bound on the capacity. In this letter: 1) we show that when L = 2 the upper bound is exact, i.e., the capacity is (1/3) and 2) for this case we give an explicit construction of optimal linear index codes to achieve this capacity by using interference alignment.

关键词： Topological interference management index coding interference alignment

来源：评论

学校读者我要写书评

暂无评论

Lattice index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第12期61卷 6505-6525页

作者： Natarajan, Lakshmi Hong, Yi Viterbo, Emanuele Monash Univ Dept Elect & Comp Syst Engn Clayton Vic 3800 Australia

The index coding problem involves a sender with K messages to be transmitted across a broadcast channel, and a set of receivers each of which demands a subset of the K messages while having a prior knowledge of a different subset as side information. We consider the specific case of noisy index coding where the broadcast channel is Gaussian and every receiver demands all the messages from the source. Instances of this communication problem arise in wireless relay networks, sensor networks, and retransmissions in broadcast channels. We construct lattice index codes for this channel by encoding the K messages individually using K modulo lattice constellations and transmitting their sum modulo a coarse lattice. We introduce a design metric called side information gain that measures the advantage of a code in utilizing the side information at the receivers, and hence, its goodness as an index code. Based on the Chinese remainder theorem, we then construct lattice index codes with large side information gains using lattices over the following principal ideal domains: 1) rational integers;2) Gaussian integers;3) Eisenstein integers;and 4) Hurwitz quaternions. Among all lattice index codes constructed using any densest lattice of a given dimension, our codes achieve the maximum side information gain. Finally, using an example, we illustrate how the proposed lattice index codes can benefit Gaussian broadcast channels with more general message demands.

关键词： Chinese remainder theorem Gaussian broadcast channel index coding lattice codes principal ideal domain side information

来源：评论

学校读者我要写书评

暂无评论

Linear index coding With Multiple Senders and Extension to a Cellular Network

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第12期67卷 8666-8677页

作者： Kim, Jae-Won No, Jong-Seon Seoul Natl Univ INMC Dept Elect & Comp Engn Seoul 08826 South Korea

In this paper, linear index codes with multiple senders are studied, where every receiver receives encoded messages from all senders. A new fitting matrix for the multiple senders is proposed and it is proved that the minimum rank of the proposed fitting matrices is the optimal codelength of linear index codes for the multiple senders. In addition, a new type of a side information graph related with the optimal codelength is proposed and whether given side information is critical or not is studied. Furthermore, linear index codes for the cellular network scenario are studied, where each receiver can receive a subset of sub-codewords. Since some receivers cannot receive the entire codeword in the cellular network scenario, the encoding method based on the fitting matrix has to be modified. In the cellular network scenario, we propose another fitting matrix and prove that an optimal generator matrix can be found based on these fitting matrices. In addition, some properties on the optimal codelength of linear index codes for the cellular network case are studied.

关键词： Cellular network fitting matrix index coding multiple senders side information

来源：评论

学校读者我要写书评

暂无评论

An index coding Approach to Caching With Uncoded Cache Placement

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第3期66卷 1318-1332页

作者： Wan, Kai Tuninetti, Daniela Piantanida, Pablo Univ Paris Sud Cent Supelec French Natl Ctr Sci Res CNRS L2S F-91192 Gif Sur Yvette France Tech Univ Berlin Elect Engn & Comp Sci Dept D-10587 Berlin Germany Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA Univ Paris Sud French Natl Ctr Sci Res CNRS F-91192 Gif Sur Yvette France Univ Montreal MILA Montreal PQ H3T 1N8 Canada

Caching is an efficient way to reduce network traffic congestion during peak hours, by storing some content at the user's local cache memory, even without knowledge of user's later demands. Maddah-Ali and Niesen proposed a two-phase (placement phase and delivery phase) coded caching strategy for broadcast channels with cache-aided users. This paper investigates the same model under the constraint that content is placed uncoded within the caches, that is, when bits of the files are simply copied within the caches. When the cache contents are uncoded and the users' demands are revealed, the caching problem can be connected to an index coding problem. This paper focuses on deriving fundamental performance limits for the caching problem by using tools for the index coding problem that were either known or are newly developed in this work. First, a converse bound for the caching problem under the constraint of uncoded cache placement is proposed based on the "acyclic index coding converse bound." This converse bound is proved to be achievable by the Maddah-Ali and Niesen's scheme when the number of files is not less than the number of users, and by a newly derived index coding achievable scheme otherwise. The proposed index coding achievable scheme is based on distributed source coding and strictly improves on the widely used "composite (index) coding" achievable bound and its improvements, and is of independent interest. An important consequence of the findings of this paper is that advancements on the coded caching problem posed by Maddah-Ali and Niesen are thus only possible by considering strategies with coded placement phase. A recent work by Yu et al has however shown that coded cache placement can at most half the network load compared to the results presented in this paper.

关键词： Coded caching uncoded cache placement index coding distributed source coding

来源：评论

学校读者我要写书评

暂无评论

Embedded index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第3期67卷 1461-1477页

作者： Porter, Alexandra Wootters, Mary Stanford Univ Dept Comp Sci Stanford CA 94305 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA

Motivated by applications in distributed storage and distributed computation, we introduce embedded index coding (EIC). EIC is a type of distributed index coding in which nodes in a distributed system act as both broadcast senders and receivers of information. We show how linear embedded index coding is related to linear index coding in general, and give characterizations and bounds on the communication costs of optimal embedded index codes. We also define task-based EIC, in which there is only one sender node responsible for transmitting a block to a particular receiving node. Task-based EIC is more computationally tractable and has advantages in applications such as distributed storage, in which senders may complete their broadcasts at different times. Finally, we give heuristic algorithms for approximating optimal linear embedded index codes, and demonstrate empirically that these algorithms perform well.

关键词： indexes Encoding Task analysis Receivers Computational modeling Peer-to-peer computing Approximation algorithms index coding distributed storage coded computation

来源：评论

学校读者我要写书评

暂无评论

index coding with outerplanar side information

Index coding with outerplanar side information

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Berliner, Y. Langberg, M. Open Univ Israel Div Comp Sci Raanana Israel

ISBN: (纸本)9781457705953

We study the index coding problem with side information graphs which are outerplanar. For general side information graphs, linearly solving the index coding problem implies a linear solution to the general (non-multicast) Network coding problem - a central open problem in the field of network communication. For outerplanar side information graphs, we show that the index coding problem can be solved efficiently, and characterize its solution in terms of the clique cover size of the information graph at hand.

关键词： Channel coding Complexity theory Computer science Face indexes Network coding clique cover size graph theory index coding network coding network communication nonmulticast network coding problem outerplanar side information graphs

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：