Distributed link scheduling with constant overhead

This paper proposes a new class of simple, distributed algorithms for scheduling in wireless networks. The algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. The class is parameterized by integers k≥ 1. We show that algorithm k of our class achieves k/(k+2) of the capacity region, for every k≥ 1. .