1Maximal 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 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. I