NDLI: Coded cooperative data exchange problem for general topologies

Content Provider	IEEE Xplore Digital Library
Author	Gonen, M. Langberg, M.
Copyright Year	2012
Description	Author affiliation: Department of Mathematics, Bar-Ilan University (Gonen, M.) \|\| Department of Mathematics and Computer Science, The Open University of Israel (Langberg, M.)
Abstract	We consider the coded cooperative data exchange problem for general graphs. In this problem, given a graph G =(V, E) representing clients in a broadcast network, each of which initially hold a (not necessarily disjoint) set of information packets; one wishes to design a communication scheme in which eventually all clients will hold all the packets of the network. Communication is performed in rounds, where in each round a single client broadcasts a single (possibly encoded) information packet to its neighbors in G. The objective is to design a broadcast scheme that satisfies all clients with the minimum number of broadcast rounds. The coded cooperative data exchange problem has seen significant research over the last few years; mostly when the graph G is the complete broadcast graph in which each client is adjacent to all other clients in the network, but also on general topologies, both in the fractional and integral setting. In this work we focus on the integral setting in general undirected topologies G. We tie the data exchange problem on G to certain well studied combinatorial properties of G and in such show that solving the problem exactly or even approximately within a multiplicative factor of log \|V\| is intractable (i.e., NP-Hard). We then turn to study efficient data exchange schemes yielding a number of communication rounds comparable to our intractability result. Our communication schemes do not involve encoding, and in such yield bounds on the coding advantage in the setting at hand.
Starting Page	2606
Ending Page	2610
File Size	132091
Page Count	5
File Format	PDF
ISBN	9781467325806
ISSN	21578117
e-ISBN	9781467325790
e-ISBN	9781467325783
DOI	10.1109/ISIT.2012.6283990
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-07-01
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation methods Approximation algorithms Encoding Topology Algorithm design and analysis Polynomials Standards
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Coded Cooperative Data Exchange Problem for General Topologies

Coded Cooperative Data Exchange Problem for General Topologies

On error correcting algorithms for the cooperative data exchange problem

Finite length analysis of caching-aided coded multicasting

Approximation algorithms design for disk partial covering problem

Coded Cooperative Data Exchange Problem for General Topologies

LP-Based Algorithms for Capacitated Facility Location

Approximation algorithms for the Street sweeping problem

Analysis of population-based evolutionary algorithms for the vertex cover problem

Coded cooperative data exchange problem for general topologies

Similar Documents

Coded Cooperative Data Exchange Problem for General Topologies

Coded Cooperative Data Exchange Problem for General Topologies

On error correcting algorithms for the cooperative data exchange problem

Finite length analysis of caching-aided coded multicasting

Approximation algorithms design for disk partial covering problem

Coded Cooperative Data Exchange Problem for General Topologies

LP-Based Algorithms for Capacitated Facility Location

Approximation algorithms for the Street sweeping problem

Analysis of population-based evolutionary algorithms for the vertex cover problem

Coded cooperative data exchange problem for general topologies