Approximation algorithms for channel allocation problems in broadcast networks

Rajiv Gandhi, Samir Khuller, Aravind Srinivasan, Nan Wang

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem, there are users who request subsets of items. There are a fixed number of channels that can carry an arbitrary amount of information. Each user must get all of the requested items from one channel, i.e., all the data items of each request must be broadcast on some channel. The load on any channel is the number of items that are broadcast on that channel; the objective is to minimize the maximum load on any channel. We present approximation algorithms for this problem and also show that the problem is MAX-SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick (Networks, 41:13-23, 2003). Each channel here can deliver information to at most k users, and we aim to minimize the total load on all channels. We present an O(n1/3)-approximation algorithm and also show that the algorithm can be made fully distributed with the same approximation guarantee; we also generalize to the case of hypergraphs.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsSanjeev Asora, Amit Sahai, Klaus Jansen, Jose D.P. Rolim
PublisherSpringer Verlag
Pages47-58
Number of pages12
ISBN (Print)3540407707, 9783540407706
DOIs
StatePublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2764
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximation algorithms for channel allocation problems in broadcast networks'. Together they form a unique fingerprint.

  • Cite this

    Gandhi, R., Khuller, S., Srinivasan, A., & Wang, N. (2003). Approximation algorithms for channel allocation problems in broadcast networks. In S. Asora, A. Sahai, K. Jansen, & J. D. P. Rolim (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 47-58). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764). Springer Verlag. https://doi.org/10.1007/978-3-540-45198-3_5