  Throughput optimal scheduling policies in general require the solution of a
complex and often NP-hard optimization problem. Related literature has shown
that in the context of time-varying channels, randomized scheduling policies
can be employed to reduce the complexity of the optimization problem but at the
expense of a memory requirement that is exponential in the number of data
flows. In this paper, we consider a Linear-Memory Randomized Scheduling Policy
(LM-RSP) that is based on a pick-and-compare principle in a time-varying
network with $N$ one-hop data flows. For general ergodic channel processes, we
study the performance of LM-RSP in terms of its stability region and average
delay. Specifically, we show that LM-RSP can stabilize a fraction of the
capacity region. Our analysis characterizes this fraction as well as the
average delay as a function of channel variations and the efficiency of LM-RSP
in choosing an appropriate schedule vector. Applying these results to a class
of Markovian channels, we provide explicit results on the stability region and
delay performance of LM-RSP.
