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

Kanes Sutuntivorakoon; Vaneet Aggarwal; A. Salman Avestimehr; Ashutosh Sabharwal

doi:10.1109/Allerton.2011.6120251

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

Kanes Sutuntivorakoon, Vaneet Aggarwal, A. Salman Avestimehr, Ashutosh Sabharwal

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

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 subgraph 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.

Original language	English (US)
Title of host publication	2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
Pages	816-823
Number of pages	8
DOIs	https://doi.org/10.1109/Allerton.2011.6120251
State	Published - 2011
Event	2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011 - Monticello, IL, United States Duration: Sep 28 2011 → Sep 30 2011

Publication series

Name	2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011

Other

Other	2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
Country/Territory	United States
City	Monticello, IL
Period	9/28/11 → 9/30/11

ASJC Scopus subject areas

Computer Networks and Communications
Control and Systems Engineering

Access to Document

10.1109/Allerton.2011.6120251

Cite this

Sutuntivorakoon, K., Aggarwal, V., Avestimehr, A. S., & Sabharwal, A. (2011). Maximal k-clique scheduling: A simple algorithm to bound maximal independent graph scheduling. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011 (pp. 816-823). Article 6120251 (2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011). https://doi.org/10.1109/Allerton.2011.6120251

Maximal k-clique scheduling: A simple algorithm to bound maximal independent graph scheduling. / Sutuntivorakoon, Kanes; Aggarwal, Vaneet; Avestimehr, A. Salman et al.
2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011. 2011. p. 816-823 6120251 (2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sutuntivorakoon, K, Aggarwal, V, Avestimehr, AS & Sabharwal, A 2011, Maximal k-clique scheduling: A simple algorithm to bound maximal independent graph scheduling. in 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011., 6120251, 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011, pp. 816-823, 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011, Monticello, IL, United States, 9/28/11. https://doi.org/10.1109/Allerton.2011.6120251

Sutuntivorakoon K, Aggarwal V, Avestimehr AS, Sabharwal A. Maximal k-clique scheduling: A simple algorithm to bound maximal independent graph scheduling. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011. 2011. p. 816-823. 6120251. (2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011). doi: 10.1109/Allerton.2011.6120251

Sutuntivorakoon, Kanes ; Aggarwal, Vaneet ; Avestimehr, A. Salman et al. / Maximal k-clique scheduling : A simple algorithm to bound maximal independent graph scheduling. 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011. 2011. pp. 816-823 (2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011).

@inproceedings{e19acb7cc6824fbd91bdb6b60602847a,

title = "Maximal k-clique scheduling: A simple algorithm to bound maximal independent graph scheduling",

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 subgraph 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.",

author = "Kanes Sutuntivorakoon and Vaneet Aggarwal and Avestimehr, {A. Salman} and Ashutosh Sabharwal",

year = "2011",

doi = "10.1109/Allerton.2011.6120251",

language = "English (US)",

isbn = "9781457718168",

series = "2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011",

pages = "816--823",

booktitle = "2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011",

note = "2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011 ; Conference date: 28-09-2011 Through 30-09-2011",

}

TY - GEN

T1 - Maximal k-clique scheduling

T2 - 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011

AU - Sutuntivorakoon, Kanes

AU - Aggarwal, Vaneet

AU - Avestimehr, A. Salman

AU - Sabharwal, Ashutosh

PY - 2011

Y1 - 2011

N2 - 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 subgraph 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.

AB - 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 subgraph 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.

UR - http://www.scopus.com/inward/record.url?scp=84856086640&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84856086640&partnerID=8YFLogxK

U2 - 10.1109/Allerton.2011.6120251

DO - 10.1109/Allerton.2011.6120251

M3 - Conference contribution

AN - SCOPUS:84856086640

SN - 9781457718168

T3 - 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011

SP - 816

EP - 823

BT - 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011

Y2 - 28 September 2011 through 30 September 2011

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this