  We consider the following basic link capacity (a.k.a., one-shot scheduling)
problem in wireless networks: Given a set of communication links, find a
maximum subset of links that can successfully transmit simultaneously. Good
performance guarantees are known only for deterministic models, such as the
physical model with geometric (log-distance) pathloss. We treat this problem
under stochastic shadowing under general distributions, bound the effects of
shadowing on optimal capacity, and derive constant approximation algorithms. We
also consider temporal fading under Rayleigh distribution, and show that it
affects non-fading solutions only by a constant-factor. These can be combined
into a constant approximation link capacity algorithm under both time-invariant
shadowing and temporal fading.
