On achieving local view capacity via maximal independent graph scheduling

Vaneet Aggarwal, A. Salman Avestimehr, Ashutosh Sabharwal

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


"If we know more, we can achieve more." This adage also applies to communication networks, where more information about the network state translates into higher sum-rates. In this paper, we formalize this increase of sum-rate with increased knowledge of the network state. The knowledge of network state is measured in terms of the number of hops, h, of information available to each transmitter and is labeled as h-local view. To understand how much capacity is lost due to limited information, we propose to use the metric of normalized sum-capacity, which is the h -local view sum-capacity divided by global-view sum capacity. For the cases of one and two-local view, we characterize the normalized sum-capacity for many classes of deterministic and Gaussian interference networks. In many cases, a scheduling scheme called maximal independent graph scheduling is shown to achieve normalized sum-capacity. We also show that its generalization for 1-local view, labeled coded set scheduling, achieves normalized sum-capacity in some cases where its uncoded counterpart fails to do so.

Original languageEnglish (US)
Article number5752418
Pages (from-to)2711-2729
Number of pages19
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - May 2011


  • Coded set scheduling
  • interference network
  • local view
  • maximal independent graph scheduling
  • maximal independent set scheduling
  • normalized sum-capacity
  • normalized sum-rate

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'On achieving local view capacity via maximal independent graph scheduling'. Together they form a unique fingerprint.

Cite this