Maximal k-Clique Scheduling: A simple algorithm to bound maximal independent graph scheduling

Kanes Sutuntivorakoon, Vaneet Aggarwal, Amir Salman Avestimehr, Ashutosh Sabharwal

Abstract

In this paper, we study interference networks with local views, where each node only knows the channel gains of h hops around them, leading to mismatched knowledge about the network. For networks with a local view, we propose a new sub-network scheduling called Maximal k-Clique Scheduling (MCS). A key benefit of MCS is that it can be explicitly constructed and hence easier to analyze compared to prior sub- graph schedulers. Our main result is that MCS can be used to bound the performance from above and below of a more complex sub-graph scheduling algorithm, known as Maximal Independent Graph Scheduling (MIGS), which in many cases does not have a known explicit construction.
BibTeX
@inproceedings{sutuntivorakoon2011maximal,
  author = {Kanes Sutuntivorakoon and Vaneet Aggarwal and Amir Salman Avestimehr and Ashutosh Sabharwal},
  title = {{Maximal k-Clique Scheduling: A simple algorithm to bound maximal independent graph scheduling}},
  booktitle = {Allerton},
  year = {2011},
  doi = {10.1109/allerton.2011.6120251},
}

Loading related content...

Figure