  Efficient link scheduling in a wireless network is challenging. Typical
optimal algorithms require solving an NP-hard sub-problem. To meet the
challenge, one stream of research focuses on finding simpler sub-optimal
algorithms that have low complexity but high efficiency in practice. In this
paper, we study the performance guarantee of one such scheduling algorithm, the
Longest-Queue-First (LQF) algorithm. It is known that the LQF algorithm
achieves the full capacity region, $\Lambda$, when the interference graph
satisfies the so-called local pooling condition. For a general graph $G$, LQF
achieves (i.e., stabilizes) a part of the capacity region, $\sigma^*(G)
\Lambda$, where $\sigma^*(G)$ is the overall local pooling factor of the
interference graph $G$ and $\sigma^*(G) \leq 1$. It has been shown later that
LQF achieves a larger rate region, $\Sigma^*(G) \Lambda$, where $\Sigma^ (G)$
is a diagonal matrix. The contribution of this paper is to describe three new
achievable rate regions, which are larger than the previously-known regions. In
particular, the new regions include all the extreme points of the capacity
region and are not convex in general. We also discover a counter-intuitive
phenomenon in which increasing the arrival rate may sometime help to stabilize
the network. This phenomenon can be well explained using the theory developed
in the paper.
