# How Well Can Graphs Represent Wireless Interference?

Magnús M. Halldórsson Tigran Tonoyan

ICE-TCS, School of Computer Science
Reykjavik University
mmh<EMAIL_ADDRESS>
Efficient use of a wireless network requires that transmissions be grouped
into feasible sets, where feasibility means that each transmission can be
successfully decoded in spite of the interference caused by simultaneous
transmissions. Feasibility is most closely modeled by a signal-to-
interference-plus-noise (SINR) formula, which unfortunately is conceptually
complicated, being an asymmetric, cumulative, many-to-one relationship.

We re-examine how well graphs can capture wireless receptions as encoded in
SINR relationships, placing them in a framework in order to understand the
limits of such modelling. We seek for each wireless instance a pair of graphs
that provide upper and lower bounds on the feasibility relation, while aiming
to minimize the gap between the two graphs. The cost of a graph formulation is
the worst gap over all instances, and the price of (graph) abstraction is the
smallest cost of a graph formulation.

We propose a family of conflict graphs that is parameterized by a non-
decreasing sub-linear function, and show that with a judicious choice of
functions, the graphs can capture feasibility with a cost of
$O(\log^{*}\Delta)$, where $\Delta$ is the ratio between the longest and the
shortest link length. This holds on the plane and more generally in doubling
metrics. We use this to give greatly improved
$O(\log^{*}\Delta)$-approximation for fundamental link scheduling problems
with arbitrary power control.

We explore the limits of graph representations and find that our upper bound
is tight: the price of graph abstraction is $\Omega(\log^{*}\Delta)$. We also
give strong impossibility results for general metrics, and for approximations
in terms of the number of links.

##  1 Introduction

Wireless scheduling. At the heart of any wireless network is a mechanism for
managing _interference_ between simultaneous transmissions. The medium access
(MAC) layer manages access to the shared resource, the wireless spectrum,
balancing the aim of maximizing simultaneous use with the impact of the
resulting interference. We can represent a transmission as a communication
_link_ , a sender-receiver pair of nodes in a metric space. Wireless
scheduling mechanisms assign the links to different “slots”, involving
different frequencies, phases and/or time steps.

The model of communication that most closely captures actual conditions,
nicknamed the _physical model_ , uses a formula based on the ratio of the
(intended) signal strength to the received interference strength (SINR) to
determine if decoding is successful. A subset $X$ of links is _feasible_ if
there exists a power assignment to the senders such that each link $i$
satisfies the SINR formula $\frac{\sum_{j\in X}I_{ji}+N}{S_{i}}\leq\beta^{-1}$
within its subset, where $S_{i}$ is the received signal strength on link $i$,
$\beta$ and $N$ are fixed constants (dependent on technology and environment),
and $I_{ji}$ is the interference strength of link $j$ on link $i$ [15] (see
Sec. 5 for full definitions). We can avoid dealing directly with power
assignments using a condition for feasibility due to Kesselheim [28] (and
shown here to be necessary). The point remains, however, that the feasibility
predicate is an asymmetric, cumulative, many-to-one relationship.

Capturing interference with graphs. The aim of this work is to capture the
complex feasibility relationship of the physical model with _graphs_ , a much
more amenable and better studied model. Preferably, a feasible set of links
should correspond to an _independent set_ in the graph on the links, and vice
versa, but since exact capture is impossible, we seek instead approximate
representations. Specifically, we want a formulation that constructs a _pair_
of graphs that bound feasibility both from below and from above. The two
graphs should also be “close” in some sense; specifically we want an
independent set in the lower bound graph to induce a low chromaticity subgraph
in the upper bound graph. That is, given a set $L$ of links, form graphs
$G_{l}(L)$ and $G_{u}(L)$ on $L$ such that:

  * •

If $S$ is feasible subset of links, then it is an independent set in
$G_{l}(L)$,

  * •

If $S$ is an independent set in $G_{u}(L)$, then $S$ is feasible set of links,
and

  * •

Chromatic numbers of the subgraphs induced by a subset $S$ are close, or
$\max_{S\subseteq L}\frac{\chi(G_{u}[S])}{\chi(G_{l}[S])}\leq\rho$.

We may dub the worst ratio $\rho$ over all instances as the _cost_ of that
graph formulation, the price we pay for using that simpler pairwise and binary
graph representation. The least such cost over all graph formulation can then
be called the _price of (graph) abstraction_.

Our results. We propose a family of conflict graph representations,
parameterized by a sub-linear, non-decreasing function $f$. It generalizes
known families, e.g., disc graphs correspond to linear functions $f$ and
pairwise feasibility is captured by constant functions. The graphs in the
family have a structural property that allows for effective approximability.
We argue that this family captures all meaningful conflict graph
representations, modulo constant factors. Our main positive result is that for
the right choice of $f$, our conflict graph representation has a cost of
$O(\log^{*}\Delta)$, where $\Delta$ is the ratio between longest and the
shortest link length. We also show that all meaningful representations must
pay this $\log^{*}\Delta$ factor. Thus, the price of abstraction, for the SINR
model with arbitrary power control, is $\Theta(\log^{*}\Delta)$. The upper
bounds hold for planar instances, and more generally in doubling metrics,
while the lower bounds are on the line. We also find that no such results are
possible in general metrics nor in terms of the parameter $n$, the number of
links.

We apply our formulations to obtain greatly improved bounds for fundamental
wireless scheduling problems. In the link Scheduling problem, we want to
partition a given set of links into fewest possible feasible sets. In the
_weighted capacity_ problem, WCapacity, the links have associated positive
weight, and we want to find the maximum weight feasible subset. In both cases,
our $O(\log^{*}\Delta)$-approximations are the first sub-logarithmic
approximations known.

Related work. Gupta and Kumar [15] proposed the geometric version of the SINR
model, where signal decays as a fixed polynomial of distance; it has since
been the default in analytic and simulations studies. They also initiated the
average-case analysis of network capacity, giving rise to a large body on
“scaling laws”. Moscibroda and Wattenhofer [37] initiated worst-case analysis
in the SINR model.

Graph-based models of wireless communication have been very common in the
past. Most common are geometric graphs involving circular ranges: _unit-disc
graphs_ (UDG) have all ranges of the same radius, while in _disc graphs_ , the
radius can vary with the power assigned, and in the _protocol_ model [15] the
communication and interference ranges are different. Various attempts have
been made to add realism, such as with 2-hop model, or _quasi-unit disc
graphs_ [2, 33], and the recently studied model of _dual graphs_ [32] captures
arbitrary unreliability in networks. None of these known models offers though
any guarantees on fidelity for representing SINR relationships, see e.g. [38].
Graph formulations for modeling SINR relationships were given previously in
[17] followed by [46], but the cost factor was either
$O(\log\log\Delta\cdot\log n)$ or $O(\log\Delta)$.

Early work on the Scheduling problem includes [5, 7, 4, 13]. NP-completeness
results have been given for different variants [13, 27, 34], but as of yet no
APX-hardness or stronger lower bounds are known for any related problem in
geometric settings, perhaps indicating the difficulty of dealing with the SINR
constraints. The related Capacity problem, where we seek to find a maximum
feasible subset of links, admits constant-factor approximation [28]. This
immediately implies a $O(\log n)$-approximation for Scheduling, where $n$ is
the number of links. Another approach is to solve links of similar lengths in
groups, which results in a $O(\log\Delta)$-approximation [13, 11, 17]. The
question of improved approximation for Scheduling has been frequently cited as
perhaps the most fundamental open problem in the field [35, 25, 10, 12, 16].
The WCapacity problem has applications in several extensions of unit-demand
link scheduling problems, such as _stochastic packet scheduling_ [44, 41, 30],
_general demand vectors, multi-path flow_ etc. [47]. A more general variant of
this problem has been considered in the framework of _combinatorial auctions_
[24, 23]. Scheduling and WCapacity have also been considered with _fixed
oblivious power assignments_ [21, 8, 17, 19, 9], but the only known sub-
logarithmic approximations are known in the case of the _linear power scheme_
[19, 45].

Issues of models. A wide range of areas in computer science and mathematics
deal with finding simpler abstractions of complex phenomena. Some examples
include: a) discrepancy theory, b) dimensionality reductions and embeddings,
c) graph augmentations and sandwiching properties, d) graph sparsification, e)
curve fitting (including least squares, finite methods, and regression), f)
approximation theory (in math), including generalized Fourier series and
Chebyshev polynomials, and g) PAC learning.

There are tradeoffs between the accuracy of a model and its complexity of
detail. There are legitimate concerns that models and problem formulations are
sometimes overly detailed and “brittle”, possibly exceeding reasonable levels
of precision (see, e.g., discussion in [39]). The benefits of a coarser model
tend to include simpler algorithms, easier analysis, but also less sensitivity
to incidental details that may or may not be modelable.

A case in point is the SINR model, which has its issues. Whereas the
additivity of interference and the near-threshold nature of signal reception
has been borne out in experiments, the geometric decay assumption is far off
in essentially all actual environments [43, 36, 42, 14]. One practical
alternative is to use facts-on-the-ground in the form of signal strength
measurements, instead of the prescriptive distance-based formula [14, 3]. To
model that formally, the pessimistic reaction would be to replace the distance
assumption with an arbitrary signal-quality matrix, but that runs into the
computational intractability monster, since such a formulation can encode the
coloring problem in general graphs [12]. A more moderate approach is to relax
the Euclidean assumption to more general metric spaces [9]. The determinacy of
the model is another issue. To capture the probabilistic factors observed in
the capture of transmissions, one approach is to extend the basic SINR model
accordingly, such as with Rayleigh fading; in that case, it has been shown
that applying algorithms based on the deterministic formula results in nearly
equally good results in that probabilistic setting [6].

Our results suggest that a reassessment of the role of graphs as wireless
models might be in order. By paying a small factor (recalling, as well, that
$\log^{*}(x)\leq 5$ in this universe), we can work at higher levels of
abstraction, with all the algorithmic and analytical benefits that it accrues.
At the same time, hopes for fully constant-factor approximation algorithms for
core scheduling problems have receded. It remains to be seen what abstractions
are possible for other related settings, especially the case of uniform power.

Roadmap to the rest of the paper. Following the basic definitions in Sec. 2,
we derive from first principles what properties link conflict graphs must
satisfy (Sec. 3). This can be read independently of the rest of the paper. We
next derive (in Sec. 4) two key properties of the family of graphs: how their
chromatic numbers relate and how their colorings can be approximated. We then
introduce the definitions of the SINR model before starting the technical core
of the paper. In Sec. 6, we show that feasibility is captured by two members
of our conflict graph family. The implications are discussed in Sec. 7: our
main upper bound result, i.e. $O(\log^{*}{\Delta})$-approximation for
Scheduling and WCapacity; a necessary and sufficient condition for
feasibility; and an explicit polynomial-time computable measure of
interference. Limitation results are given in Sec. 8, in particular that no
better bounds are possible via conflict graphs. For space reasons, only
sketches of the proofs are given in this extended abstract.

##  2 Definitions: Metrics, Functions, Graphs

Communication Links. Consider a set $L$ of $n$ _links_ , numbered from $1$ to
$n$. Each link $i$ represents a unit-demand communication request from a
sender $s_{i}$ to a receiver $r_{i}$ — point-size wireless
transmitter/receivers (nodes) located in a metric space with distance function
$d$. We denote $d_{ij}=d(s_{i},r_{j})$ and refer to $l_{i}=d(s_{i},r_{i})$ as
the _length_ of link $i$. We let $\Delta(L)$ denote the ratio between the
longest and the shortest link lengths in $L$, and drop $L$ when clear from
context. We shall assume in the rest of the paper that all link lengths are
distinct, which can be achieved by arbitrarily (but consistently) breaking
ties as needed. For sets $S_{1},S_{2}$ of links, we let $d(S_{1},S_{2})$
denote the minimum distance between _a node_ in $S_{1}$ and a node in $S_{2}$.
In particular, we will extensively use
$d(i,j)=\min(d_{ij},d_{ji},d(s_{i},s_{j}),d(r_{i},r_{j}))$, the minimum
distance between nodes on links $i,j$.

Let $S_{i}^{+}=\\{j\in S:l_{j}>l_{i}\\}$ denote the subset of links in a set
$S$ that are longer than link $i$, and similarly $S_{i}^{-}=\\{j\in
S:l_{j}<l_{i}\\}$ the subset of links shorter than $i$.

Doubling Metrics. The _doubling dimension_ of a metric space is the infimum of
all numbers $\delta>0$ such that for every $\epsilon$, $0<\epsilon\leq 1$,
every ball of radius $r>0$ has at most $C\epsilon^{-\delta}$ points of mutual
distance at least $\epsilon r$ where $C\geq 1$ is an absolute constant, and
$0<\epsilon\leq 1$. Metrics with finite doubling dimensions are said to be
_doubling_. For example, the $m$-dimensional Euclidean space has doubling
dimension $m$ [22]. We let $m$ denote the doubling dimension of the space
containing the links.

Functions. A function $f$ is _sub-linear_ if $f(x)=O(x)$. A function $f$ is
_strongly sub-linear_ if for each constant $c\geq 1$, there is a constant
$c^{\prime}$ such that $cf(x)/x\leq f(y)/y$ for all $x,y\geq 1$ with $x\geq
c^{\prime}y$. Note that if $f$ is strongly sub-linear then $f(x)=o(x)$.
Examples. The functions $f(x)=x^{1-\epsilon}$ for any constant $\epsilon>0$
and $f(x)=\log{x}$ are strongly sub-linear111When not otherwise identified,
logarithms are base 2., while $f(x)=x/\log{x}$ is not strongly sub-linear even
though $f(x)=o(x)$.

Let $f$ be a strongly sub-linear function. For each integer $c\geq 1$, the
function $f^{(c)}(x)$ is defined inductively by: $f^{(1)}(x)=f(x)$ and
$f^{(c)}(x)=f(f^{(c-1)}(x))$. Let $x_{0}=\inf\\{x\geq 1,f(x)<x\\}+1$; such a
point exists for any $f(x)=o(x)$. The function _iterated $f$_, denoted
$f^{*}(x)$, is defined by:

$f^{*}(x)=\begin{cases}\min_{c}\\{f^{(c)}(x)\leq x_{0}\\},&\text{if
}x>x_{0},\\\ 1,&\text{otherwise.}\end{cases}$

Examples.  For $f(x)=\log{x}$, $f^{*}(x)=\log^{*}{x}$ is the well known
_iterated logarithm_. It is also easy to check that for $f(x)=\log^{(c)}{x}$,
$f^{*}(x)=\lceil\frac{\log^{*}{x}}{c}\rceil$ and for $f(x)=\sqrt{x}$,
$f^{*}(x)=\lceil\log{\log{x}}\rceil$. Note also that
$g^{*}(x)=\Theta(f^{*}(x))$ if $g(x)=cf(x)$ for a constant $c>0$.

Graphs. For a graph $G$ and a vertex $v$, $N_{G}(v)$ denotes the neighborhood
of $v$ in $G$, i.e., the set of vertices adjacent with $v$. $\chi(G)$ denotes
the chromatic number of graph $G$, the minimum number of colors needed for a
proper (vertex) coloring of $G$.

A _$d$ -inductive order_ of a graph is an arrangement of the vertices from
left to right such that each vertex has at most $d$ _post-neighbors_ , or
neighbors appearing to its right. A _$k$ -simplicial elimination order_ is one
where the post-neighbors of each vertex can be covered with $k$ cliques. A
graph is $d$-inductive ($k$-simplicial) if it has a $d$-inductive
($k$-simplicial elimination) order. It is well known that a $d$-inductive
graphs are $d+1$-colorable, while the coloring and weighted maximum
independent set problems are $k$-approximable in $k$-simplicial graphs [1, 26,
49]. The only inductive or simplicial order we consider for conflict graphs is
the _increasing order_ of links by length.

##  3 Formulations of Conflict Graphs

What kind of graphs are conflict graphs? By a “conflict graph formulation” we
mean a deterministic rule for forming graphs on top of a set of links. For it
to be meaningful as a general purpose mechanism, such a formulation cannot be
too context sensitive. We shall postulate some axioms (that by nature should
be self-evident) that lead to a compact description of the space of possible
conflict graph formulations.

######  Axiom 1.

A conflict graph formulation is defined in terms of the _pairwise
relationship_ of links.

By nature, graphs represent pairwise relationships; conflict graphs
formulations are boolean predicates of pairs of links. More specifically,
though, we expect the conflict graph to be defined in terms of the relative
standings of the link pairs. That is, the existence of an edge between link
$i$ and link $j$ should depend only on the properties of the two links, not on
other links in the instance. The only properties of note are the ${4\choose
2}=6$ distances between the nodes in the links.

We refer to a _conflict_ between two links if the formulation specifies them
to be adjacent in the conflict graph; otherwise, they are _conflict-free_.

######  Axiom 2.

A conflict graph formulation is _independent of positions and scale_.
Translating distances or scaling them by a fixed factor does not change the
conflict relationship.

It is an essential feature of the SINR formula (that distinguishes it from
other formulations, like unit-disc graphs) is that only relative distances
matter. Thus, the positions of the nodes should not matter, only the pairwise
distances, and only the relative factors among the distances. There is a
practical limit to which links can truly grow, due to the ambient noise term.
However, that only matters when lengths are very close to that limit; we will
treat that case separately.

As a result of this axiom, we can factor out the length of the shorter of the
two links considered.

######  Axiom 3.

A conflict formulation is _monotonic_ with increasing distances.

The reasoning is that a conflict formulation should represent the degree of
conflict between pairs of links, or their relative “nearness”. Specifically,
if two links conflict and their separation (i.e., one of the distances between
endpoints on distinct links) decreases while the links stay of the same
length, then the links still conflict. Similarly, if two links are conflict-
free and the length of one of them decreases (while their separation stays
unchanged), the links stay conflict-free.

######  Axiom 4.

A conflict formulation should respect pairwise incompatibility. That is, if
two (links) cannot coexist in a feasible solution, they should be adjacent in
the conflict graph.

In the case of conflict graphs for links in the SINR model with arbitrary
power control, we propose an additional axiom.

######  Axiom 5.

A conflict formulation for links under arbitrary power control is symmetric
with respect to senders and receivers.

Namely, it should not matter which endpoint of a link is the sender and which
is the receiver when determining conflicts. The key rationale for this comes
from Kesselheim’s sufficient condition for feasibility, given here as Thm. 4.
As we show in Sec. 7.3, this formula is also a necessary condition in doubling
metrics, up to constant factors. Thus, feasibility is fully characterized by a
symmetric rule (modulo constant factors).

As we shall see, the axioms and the properties of doubling metrics imply that
only two distances really matter in the formulation of conflict graphs: the
length of the longer link, and the distance between the nearest nodes on the
two links (both scaled by the length of the shorter link). This motivates the
following definition.

######  Definition 1.

Let $f:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ be a positive non-decreasing
sub-linear function. Two links $i,j$ are said to be _$f$ -independent_ if

$\frac{d(i,j)}{l_{min}}>f\left(\frac{l_{max}}{l_{min}}\right),$

where $l_{min}=\min\\{l_{i},l_{j}\\},l_{max}=\max\\{l_{i},l_{j}\\}$, and
otherwise they are _$f$ -adjacent_. A set of links is $f$-independent
($f$-adjacent) if they are pairwise $f$-independent ($f$-adjacent),
respectively.

Let $L$ be a set of links. The conflict graph ${\cal G}_{f}(L)$ is the graph
with vertex set $L$, where two vertices are adjacent if and only if they are
$f$-adjacent.

_Remark._ For the constant function $f(x)\equiv\gamma$ for a number $\gamma$,
we use the notation ${\cal G}_{\gamma}(L)$ for the corresponding conflict
graph.

We now argue that all conflict formulations satisfying the above axioms are
essentially of the form ${\cal G}_{f}$, for a function $f$. They can differ
from ${\cal G}_{f}$ but not by more than what can be accounted for by an
appropriate constant factor.

######  Proposition 1.

Every conflict graph formulation ${\cal K}$ is captured by ${\cal G}_{f}$, for
some non-decreasing and sub-linear function $f$. Namely, there is a constant
$\gamma$ such that ${\cal K}$ is sandwiched by ${\cal G}_{f}$ and ${\cal
G}_{\gamma f}$, i.e., ${\cal G}_{f}(L)\subseteq{\cal K}(L)\subseteq{\cal
G}_{\gamma f}(L)$, for every link set $L$.

###### Proof.

By Axiom 1, a conflict formulation ${\cal K}$ is a function of link pairs,
more specifically, the distances among the four points. By Axiom 2, we can use
normalized distances, and will choose to factor out the length of the shorter
link. By Axiom 5, it does not matter which of them involve senders and which
involve receivers.

Now, consider two links $i=(s_{i},r_{i})$ and $j=(s_{j},r_{j})$, where
$l_{i}\leq l_{j}$, and assume without loss of generality that $s_{i}$ and
$s_{j}$ are the nearest points on the two links. Let us denote for short
$d=d(i,j)=d(s_{i},s_{j})$. We aim to show that decisions regarding adjacency
in ${\cal K}$ can be determined in terms of constant multiples of $d$ and
$l_{j}$.

First, recall that by Axiom 4, pairwise incompatible links must be adjacent in
any conflict graph. Thus, as derived in Thm. 6, we may restrict attention to
the case that $d(i,j)\geq cl_{i}$, for an absolute constant $c$. In that case,
it follows that distance $d(r_{i},s_{j})$ is at most constant times the
distance from $i$ to $j$, i.e., $d(s_{i},s_{j})\leq
d(r_{i},s_{j})\leq(1+1/c)d(s_{i},s_{j})$.

Next, we claim that $d(s_{i},r_{j})$ is within a constant multiple of
$q=\max(d,l_{j}/2)$. By definition of $d$, it holds that $d(s_{i},r_{j})\geq
d$, while by the triangular inequality, $d(s_{i},r_{j})\geq
l_{j}-d(s_{i},s_{j})=l_{j}-d$. Thus, $d(s_{i},r_{j})\geq\max(d,l_{j}-d)\geq
q$. Also, by triangular inequality, $d(s_{i},r_{j})\leq d+l_{j}\leq 3q$.

Finally, for by triangular inequality, $d(r_{i},r_{j})\leq d+l_{i}+l_{j}\leq
d+2l_{j}$, and $d(r_{i},r_{j})\geq d-l_{i}-l_{j}\geq d-2l_{j}$. So, defining
$q^{\prime}=\max(d,l_{j}/4)$, we similarly obtain that $q^{\prime}\leq
d(r_{i},r_{j})\leq 9q^{\prime}$. It follows that all the five distances
between endpoints are within constant multiples of $d(i,j)$ and $l_{j}$,
relative to the shorter link length $l_{i}$.

Hence, by monotonicity (Axiom 3), ${\cal K}$ is dominated by a conflict graph
formulation ${\cal H}$ defined by a monotone boolean predicate of two
variables: length of the longer link $l_{j}$, and the distance $d(i,j)$
between the links (scaled by the shorter link). But, an arbitrary monotone
boolean predicate of two variables $x,y$ can be represented by a relationship
of the form $y>f(x)$, for some function $f$. Thus, ${\cal K}$ is dominated by
${\cal G}_{f}$, for some non-decreasing function $f$. Also, by the same
arguments, ${\cal K}$ dominates ${\cal G}_{cf}$ for a constant $c$.

Finally, sub-linearity is a necessary condition, since super-linear growth
would break Axiom 3. ∎

##  4 Properties of Conflict Graphs

We explore two types of properties of conflict graphs. The first type is
concerned with gaps between the chromatic numbers of conflict graphs, or the
relative difference of the chromatic numbers of graphs ${\cal G}_{f}$ and
${\cal G}_{f^{\prime}}$. We show that the introduction of $f$ increases the
chromatic number of ${\cal G}_{\gamma}$ by a rather small factor depending on
$f$. This is a key result that will be used to derive the approximation factor
in the main result of this paper. We also show that the introduction of
constant factor $\gamma$ changes the chromatic number of ${\cal G}_{f}$ only
by a constant factor.

In the second part we consider algorithmic properties of graphs ${\cal
G}_{f}$. In particular, we prove that graphs ${\cal G}_{f}$ are constant-
simplicial. Thus, constant factor approximation algorithms for vertex
coloring, weighted maximum independent set and several other
$\mathcal{NP}$-hard problems follow. This allows us to algorithmically
approximate feasibility with graphs.

###  4.1 Gaps Between Chromatic Numbers of Conflict Graphs

We start by showing that the difference between the chromatic numbers of
${\cal G}_{\gamma}$ and ${\cal G}_{\gamma f}$ is a factor of at most
$O(f^{*}(\Delta))$, where $f^{*}$ is the iterated $f$ function. This result is
obtained by proving that for any independent set $S$ in ${\cal
G}_{\gamma}(L)$, the graph ${\cal G}_{\gamma f}(S)$ is
$O(f^{*}(\Delta))$-inductive. To this end, we want to show that, for any given
link $i$ in $S$, any set $T$ of mutually $\gamma$-independent links in
$S^{+}_{i}$ that are $\gamma f$-neighbors of $i$ is small, or
$O(f^{*}(\Delta))$. We do so by showing that the progression of lengths of the
links in $T$ must be fast growing, or inversely with $f$; the number of links
must therefore be bounded by the iterated $f$ function.

######  Theorem 1.

For any set of links $L$, a constant $\gamma\geq 1$ and a non-decreasing
strongly sub-linear function $f$, $\chi({\cal G}_{\gamma
f}(L))=O(f^{*}(\Delta))\cdot\chi({\cal G}_{\gamma}(L))$.

###### Proof.

Let $S$ be a $\gamma$-independent set in $L$. Consider any link $i\in S$ and
let $T$ denote the set of links in $S_{i}^{+}$ that are $f$-adjacent with $i$.
We will show that $|T|=O(f^{*}(\Delta))$. Note that for each $j\in T$,
$d(i,j)\leq\gamma l_{i}f(l_{j}/l_{i})$. Let $p_{j}$ denote the endpoint of
link $j\in T$ closest to link $i$. We split $T$ into two subsets $T_{1}$ and
$T_{2}$, where

$T_{1}=\\{j\in T:d(p_{j},r_{i})\leq\gamma l_{i}f(l_{j}/l_{i})\\}\mbox{ and
}T_{2}=T\setminus T_{1}\subseteq\\{j\in T:d(p_{j},s_{i})\leq\gamma
l_{i}f(l_{j}/l_{i})\\}.$

Let us first consider $T_{1}$. Let $j,k\in T_{1}$ be two links with
$l_{k}<l_{j}$. Then,

$\displaystyle d(p_{j},r_{i})$ $\displaystyle\leq\gamma l_{i}f(l_{j}/l_{i}),$
(because $j,k\in T_{1}$) (1) $\displaystyle d(p_{k},r_{i})$
$\displaystyle\leq\gamma l_{i}f(l_{k}/l_{i}),$ (2) $\displaystyle
d(p_{j},p_{k})$ $\displaystyle\geq d(j,k)>\gamma l_{k},$ ($j,k$ are
$\gamma$-independent) (3)

By plugging the inequalities above into the triangle inequality
$d(p_{j},p_{k})\leq d(p_{j},r_{i})+d(r_{i},p_{k})$, we obtain $\gamma
l_{k}<\gamma l_{i}f(l_{j}/l_{i})+\gamma l_{i}f(l_{k}/l_{i})\leq 2\gamma
l_{i}f(l_{j}/l_{i}),$ where the last inequality follows from the assumption
that $l_{k}<l_{j}$ and that $f$ is a non-decreasing function. Thus,

$l_{k}/l_{i}<2f(l_{j}/l_{i}).$ (4)

Denote $g(x)\equiv 2f(x)$. Note that $g(x)$ is strongly sub-linear; hence,
there exists $x_{0}=\inf\\{x\geq 1,g(x)<x\\}+1$. Let $1,2,\dots,t=|T_{1}|$ be
the arrangement of the links in $T_{1}$ in increasing order by length and let
$\lambda_{j}=\frac{l_{j}}{l_{i}}$ for $j=1,2,\dots,t$. Let $h$ be the link
with the smallest index such that $\lambda_{h}\geq x_{0}$. We will bound the
number of links in $A=\\{1,2,\dots,h-1\\}$ and $B=\\{h,h+1,\dots,t\\}$
separately. $|A|$ can be bounded by a simple application of the doubling
property of the space. Note that for all $j\in A$, $f(l_{j}/l_{i})\leq
f(x_{0})=O(1)$ because $l_{j}/l_{i}<x_{0}$. Thus, the system of inequalities
(1-3) implies that the mutual distance between different points $p_{j}$ with
$j\in A$ is at least $\gamma l_{i}$, while their distance from $r_{i}$ is at
most $\gamma f(x_{0})l_{i}$; hence, we have that $|A|=O(f(x_{0})^{m})=O(1)$.

Now let us bound $|B|$, using (4). We have that

$x_{0}\leq\lambda_{h}<g(\lambda_{h+1})\leq g(g(\lambda_{h+2}))\leq\cdots\leq
g^{(t-h)}(\lambda_{t}),$

which implies that $t-h\leq g^{*}(\lambda_{t})=O(f^{*}(\Delta))$. Recall that
$h=|A|=O(1)$; hence, $t=O(f^{*}(\Delta))$.

This completes the proof that $|T_{1}|=O(f^{*}(\Delta))$. The set $T_{2}$ is
handled similarly. In this case, for any pair of links $j,k\in T_{2}$ with
$l_{j}>l_{k}$, the system of inequalities (1-3) holds with $r_{i}$ replaced
with $s_{i}$; the rest of the argument is identical. These results imply the
theorem. ∎

Next we show that the chromatic number of ${\cal G}_{f}$ is of the same order
as the chromatic number of ${\cal G}_{\gamma f}$. We prove that any
independent set $S$ in ${\cal G}_{f}$ is constant-inductive as an induced
subgraph of ${\cal G}_{\gamma f}$. To this end, we prove, using the strong
sub-linearity of $f$ (Lemma 1), that for any link $i\in S$, the set of
neighbors of $i$ in $S_{i}^{+}$ mainly consists of links of length
$\Theta(l_{i})$. The number of such links is bounded by a rather
straightforward application of the doubling property of the space, using the
fact that those links form an independent set, while at the same time are
adjacent with link $i$.

######  Lemma 1.

Let $f$ be a non-decreasing strongly sub-linear function and $i,j,k$ be links.
If links $j,k$ are longer than $i$, are $f$-independent and are $\gamma
f$-adjacent with $i$, then $\min\\{l_{j},l_{k}\\}\leq cl_{i}$, where the
constant $c$ depends only on function $f$ and constant $\gamma$.

###### Proof.

Assume without loss of generality that $l_{k}<l_{j}$. Since $f$ is strongly
sub-linear, there is a constant $c>0$ such that $2\gamma f(x)/x\leq f(y)/y$
whenever $x\geq cy$. We will show that $l_{k}\leq cl_{i}$. Let us assume, for
contradiction, $l_{k}>cl_{i}$. Let $p_{j}$ ($p_{k}$) denote the endpoint of
link $j$ (link $k$) closest to link $i$. Then,

$\displaystyle d(p_{j},r_{i})$ $\displaystyle\leq\gamma l_{i}f(l_{j}/l_{i}),$
($j,k$ are $\gamma f$-adjacent with $i$) (5) $\displaystyle d(p_{k},r_{i})$
$\displaystyle\leq\gamma l_{i}f(l_{k}/l_{i}),$ (6) $\displaystyle
d(p_{j},p_{k})$ $\displaystyle\geq d(j,k)>l_{k}f(l_{j}/l_{k}),$
$\displaystyle\text{ ($j,k$ are $f$-independent)}.$ (7)

By plugging these inequalities into the triangle inequality we get:

$l_{k}f(l_{j}/l_{k})<d(p_{j},p_{k})\leq
d(p_{j},r_{i})+d(r_{i},p_{k})\leq\gamma l_{i}f(l_{j}/l_{i})+\gamma
l_{i}f(l_{k}/l_{i})\leq 2\gamma l_{i}f(l_{j}/l_{i}).$

Let us denote $x=l_{j}/l_{i}$ and $y=l_{j}/l_{k}$. Note that $x>cy$. The
inequality above asserts that $2\gamma f(x)/x>f(y)/y$, which contradicts the
definition of $c$. This completes the proof. ∎

######  Theorem 2.

Let $L$ be a set of links and $f$ be a non-decreasing strongly sub-linear
function. Then $\chi({\cal G}_{f}(L))=\Theta(\chi({\cal G}_{\gamma f}(L)))$
for any constant $\gamma>0$.

###### Proof.

We assume w.l.o.g. that $\gamma\geq 1$. Thus, we only need to show that
$\chi({\cal G}_{\gamma f}(L))=O(\chi({\cal G}_{f}(L)))$. Consider any
independent set $S$ in ${\cal G}_{f}(L)$. It suffices to show that ${\cal
G}_{\gamma f}(S)$ is constant-inductive. Let us fix a link $i$ and let
$T=S_{i}^{+}\cap N_{{\cal G}_{\gamma f}(S)}(i)$ denote the set of neighbors of
$i$ in ${\cal G}_{\gamma f}(S)$ that are longer than $i$. It is enough to show
that $T=O(1)$. Recall that all the links in $T$ are $\gamma f$-adjacent with
$i$ and are $f$-independent among each other. By applying Lemma 1 for all
pairs $j,k\in T$, we conclude that there is a constant $c$ such that all the
links in $T$, except perhaps one, have length at most $cl_{i}$. Let
$T^{\prime}$ be the subset of $T$ containing those links. It is enough to show
that $|T^{\prime}|=O(1)$. For each link $j\in T^{\prime}$, let $p_{j}$ denote
the endpoint of $j$ closest to link $i$. We split $T^{\prime}$ into two
subsets $T^{\prime}_{1}$ and $T^{\prime}_{2}$, where

$T^{\prime}_{1}=\\{j\in T^{\prime}:d(p_{j},r_{i})\leq\gamma
l_{i}f(l_{j}/l_{i})\\}\mbox{ and }T^{\prime}_{2}=T^{\prime}\setminus
T^{\prime}_{1}\subseteq\\{j\in T^{\prime}:d(p_{j},s_{i})\leq\gamma
l_{i}f(l_{j}/l_{i})\\}.$

We first bound $|T^{\prime}_{1}|$. Note that for each pair of links $j,k\in
T^{\prime}_{1}$ with $l_{j}>l_{k}$, the distance $d(p_{j},p_{k})$ is at least
$d(p_{j},p_{k})>l_{k}f(l_{j}/l_{k})\geq f(1)l_{i}$ because $j,k$ are
$f$-independent. On the other hand, for each $j\in T^{\prime}_{1}$, the
distance $d(p_{j},r_{i})$ is at most $d(p_{j},r_{i})\leq\gamma
l_{i}f(l_{j}/l_{i})\leq\gamma f(c)l_{i}$ because $i,j$ are $\gamma f$-adjacent
and $l_{j}\leq cl_{i}$. We conclude that $|T^{\prime}_{1}|=O((\gamma
f(c)/f(1))^{m})=O(1)$, using the doubling property of the metric space.

We can prove that $|T^{\prime}_{2}|=O(1)$ in a similar manner, by replacing
$r_{i}$ with $s_{i}$ in the formulas. These results imply the theorem. ∎

###  4.2 Algorithmic Properties of Conflict Graphs

We prove that every conflict graph ${\cal G}_{f}$ with strongly sub-linear
function $f$ is constant-simplicial. This guarantees, among other properties,
that the vertex coloring and maximum weighted independent set problems in
these graphs can be efficiently approximated within constant factors [1, 26,
49].

We give a simple argument that holds in the plane, where it holds for
essentially all sub-linear functions. It is based on splitting the plane into
$60\degree$ sectors emanating from a given node of a link, and arguing that
all adjacent longer links within a sector must form a clique. With a more
detailed argument, the result can be extended to general doubling metrics, but
requires then strong sub-linearity.

######  Proposition 2.

Let $f$ be a non-decreasing function such that $f(x)/x$ is non-increasing and
let $L$ be a set of links in the plane. Then ${\cal G}_{f}(L)$ is
12-simplicial.

###### Proof.

Consider a link $i$ and let $S\subseteq L_{i}^{+}$ be the longer neighbors of
$i$ in ${\cal G}_{f}(L)$. We partition $S$ into two sets: $S_{1}$, with links
that are closer to the sender node $s_{i}$, and $S_{2}$, the links that are
closer to $r_{i}$. Consider $S_{1}$ first. For a link $j\in S_{1}$, let
$p_{j}$ denote the endpoint of $j$ that is the closest to $s_{i}$, i.e.,
$d(i,j)=d(p_{j},r_{i})$. Then we have, from $f$-dependence, that
$d(p_{j},s_{i})\leq l_{i}\cdot f(l_{j}/l_{i})$ for all $j\in S_{1}$. Partition
the plane into six $60\degree$ sectors emanating from $s_{i}$. Let $j,k$ be
two links such that $l_{k}>l_{j}$ and $p_{j}$ and $p_{k}$ fall in the same
sector. By considering the triangle $(p_{j},p_{k},s_{i})$, we can see that the
edge $p_{j}p_{k}$ must be no longer than
$\max\\{d(p_{j},s_{i}),d(p_{k},s_{i})\\}$. Thus,

$d(j,k)\leq d(p_{j},p_{k})\leq l_{i}\cdot f(l_{k}/l_{i})\leq l_{j}\cdot
f(l_{k}/l_{j}),$

where the second inequality follows because $f(x)$ is non-decreasing and the
third one follows because $f(x)/x$ is non-increasing. This shows that the
links $j,k$ must be adjacent. Thus, $S_{1}$ can be covered with at most 6
cliques. An identical argument holds for $S_{2}$, by splitting the plane
around $r_{i}$. This completes the proof. ∎

_Remark._ The proof above cannot be replicated in general doubling metrics.
Moreover, it can be shown that there are functions $f$ such that ${\cal
G}_{f}$ is constant-simplicial in the plane, but is not so even in a one
dimensional doubling metric. The linear function $f(x)=x$ is such an example.
This claim can be demonstrated by the following example with $n+1$ points
$p_{0},p_{1},\dots,p_{n}$, where $d(p_{i},p_{0})=2^{i}$ for all $i\geq 1$ and
$d(p_{i},p_{k})=2^{i}+1$ for all $i>k\geq 1$. It is straightforwardly checked
that the points in this example form a $1$-dimensional doubling space. On the
other hand, the $f$-neighborhood of point $p_{0}$ contains a set of $\log{n}$
$f$-independent points. A similar example was also observed in [48] in a
different context. However, we prove that ${\cal G}_{f}$ is constant-
simplicial in doubling metrics for _strongly sub-linear_ functions $f$.

We show as before, that for a link $i$, the set of longer links adjacent with
$i$ can be covered with a small number of cliques. We start by showing (using
Lemma 1) that the neighbors of $i$ of length $\Omega(l_{i})$ must form a
single clique. The rest of the links (having length $O(l_{i})$) can be covered
by cliques using a simple clustering procedure. We show that the cluster-heads
must be separated by a distance $\Omega(l_{i})$, which implies, using the
doubling property of the space and the fact that all the links in
consideration are neighbors of link $i$ and have length $O(l_{i})$, that the
number of clusters (cliques) must be bounded by a constant.

######  Theorem 3.

Let $f$ be a non-decreasing strongly sub-linear function with $f(x)\geq 1$ for
all $x\geq 1$. Then for each set $L$, ${\cal G}_{f}(L)$ is constant-
simplicial.

###### Proof.

Let $i\in L$ be any link and let the subset $S\subseteq L_{i}^{+}$ consist of
links in $L$ longer than $i$ and $f$-adjacent with $i$. We show that $S$ can
be covered with a constant number of cliques.

Let $j,k\in S$ be any pair of $f$-independent links in $S$. By Lemma 1, there
is a constant $c>0$ depending only on $f$, such that at least one of the links
$j,k$ is not longer than $cl_{i}$. Thus, the set of links $j\in S$ with
$l_{j}>cl_{i}$ forms a single clique.

It remains to show that the subset of $S$ with links of length at most
$cl_{i}$ can be covered with a constant number of cliques. Let $T$ denote this
subset.

We split $T$ into a set of cliques by the following procedure. Pick an
arbitrary link $j\in T$. Let $N^{1}_{j}$ denote the set of links $k$
(including link $j$) with $\min\\{d(s_{j},s_{k}),d(s_{j},r_{k})\\}\leq
l_{i}/2$ and $N^{2}_{j}$ denote the set of links $k$ with
$\min\\{d(r_{j},s_{k}),d(r_{j},r_{k})\\}\leq l_{i}/2$. Set
$T=T\setminus(N^{1}_{j}\cup N^{2}_{j})$. Repeat until $T$ is empty. Let $R$ be
the links picked by the procedure above.

Note that for each $j\in R$, $N^{1}_{j}$ and $N^{2}_{j}$ are cliques. Indeed,
consider e.g. $N_{j}^{1}$ and let $k_{1},k_{2}\in N_{j}^{1}$ and
$l_{k_{1}}<l_{k_{2}}$. The triangle inequality and the assumption $f(x)\geq 1$
for $x\geq 1$ imply that $d(k_{1},k_{2})\leq
l_{i}<l_{k_{1}}f(l_{k_{2}}/l_{k_{1}})$, which means that $k_{1},k_{2}$ are
$f$-adjacent. Moreover, these cliques cover $T$. Let us show that $|R|=O(1)$.
For each $j\in R$, let $p_{j}$ denote the endpoint of $j$ that is closest to
$i$. We split $R$ into two subsets, $R_{1}$ and $R_{2}$ (based on the fact
that $R$ consists of links $f$-adjacent with $i$), where

$R_{1}=\\{j\in R:d(p_{j},r_{i})\leq l_{i}f(l_{j}/l_{i})\\}\mbox{ and
}R_{2}=R\setminus R_{1}\subseteq\\{j\in R:d(p_{j},s_{i})\leq
l_{i}f(l_{j}/l_{i})\\}.$

Let us consider $R_{1}$ first. Recall that for each $j\in R$, $l_{j}\leq
cl_{i}$. From the definition of $R_{1}$ we have that for each $j\in R_{1}$,
$d(p_{j},r_{i})\leq l_{i}f(l_{j}/l_{i})\leq l_{i}f(c)$, i.e., the points
$p_{j}$ are inside the ball of radius $l_{i}f(c)$ centered at $s_{i}$. On the
other hand, we have by the construction of $R$ that for any $j,k\in R$,
$d(p_{j},p_{k})\geq d(j,k)>l_{i}/2$. Hence, by applying the doubling property
of the metric space we get that
$|R_{1}|\leq(l_{i}f(c)/(l_{i}/2))^{m}=(2f(c))^{m}=O(1)$. A similar argument
holds for $R_{2}$, by replacing $r_{i}$ with $s_{i}$. Thus, we get $|R|=O(1)$,
which completes the proof. ∎

##  5 Definitions: SINR, Feasibility

Notation | Meaning | Topic | Page
---|---|---|---
$f^{(c)}(x)$ | function $f$ applied $c$ times |  | 2
$f^{*}(x)$ | iterated $f$ | Functions | 2
$\widehat{\log}(x)$ | $\approx\log^{2/(\alpha-m)}(x)$ |  | 6
$m$ | the doubling dimension of the metric space | Metric Space | 2
$d$ | the distance function of the metric space |  | 2
$n$ | the number of links |  | 2
$s_{i},r_{i}$ | sender and receiver nodes of link $i$ |  | 2
$l_{i}$ | the length of link $i$, $l_{i}=d(s_{i},r_{i})$ |  | 2
$d_{ij}$ | the distance from $s_{i}$ to $r_{j}$, $d_{ij}=d(s_{i},r_{j})$ |  | 2
$d(i,j)$ | the minimum distance between links $i,j$ | Links | 2
$\Delta(L)$ | the maximum ratio between link lengths in $L$ |  | 2
$L_{i}^{+}$ | the subset of links of $L$ longer than link $i$ |  | 2
$L_{i}^{-}$ | the subset of links of $L$ shorter than link $i$ |  | 2
$\chi(G)$ | the chromatic number of graph $G$ |  | 2
$N_{G}(v)$ | the neighborhood of vertex $v$ in graph $G$ | Graphs | 2
${\cal G}_{f}(L)$ | the $f$-adjacency graph over the set $L$ |  | 1
${\cal G}_{\gamma}(L)$ | the $f$-adjacency graph over $L$ with $f(x)=\gamma$ |  | 3
$P$ | power assignment, $P:L\rightarrow\mathbb{R}_{+}$ |  | 5
$\alpha$ | the path loss exponent |  | 5
$\beta$ | the SINR threshold value |  | 5
$N$ | the ambient noise term | SINR | 5
$OPTS(L)$ | the optimum schedule length of set $L$ |  | 7.1
$I$ | the influence operator |  | 5
$I(L)$ | same as $\max_{i\in L}{I(L_{i}^{-},i)}$ |  | 5
Table 1: Notations.

SINR Model and Feasibility. A _power assignment_ for a set $L$ of links is a
function $P:L\rightarrow\mathbb{R}_{+}$. For each link $i$, $P(i)$ defines the
power level used by the sender node $s_{i}$. In the _physical model (or SINR
model)_ of communication [40], when using a power assignment $P$, a
transmission of a link $i$ is successful if and only if

$\frac{P(i)}{l_{i}^{\alpha}}\geq\beta\cdot\left(\sum_{j\in
S\setminus\\{i\\}}\frac{P(j)}{d_{ji}^{\alpha}}+N\right),$ (8)

where $N$ is a constant denoting the ambient noise, $\beta$ denotes the
minimum SINR (Signal to Interference and Noise Ratio) required for a message
to be successfully received, $\alpha\in(2,6)$ is the path loss constant and
$S$ is the set of links transmitting concurrently with link $i$. Here the left
side of the inequality is interpreted as the received signal power of link $i$
and the sum on the right side is interpreted as the interference on link $i$
caused by concurrently transmitting links.

A set $S$ of links is called $P$-_feasible_ if the condition (8) holds for
each link $i\in S$ when using power $P$. We say $S$ is _feasible_ if there
exists a power assignment $P$ for which $S$ is $P$-feasible. Similarly, a
collection of sets is $P$-feasible/feasible if each set in the collection is.
Note that we do not assume limits on the available power, which means that the
noise term can be ignored. The case of a maximum power limit requires
primarily that the links that are close to maximum length be handled
separately using the maximum power available [29], something that remains to
be studied.

The Influence Operator and a Sufficient Condition for Feasibility. The
_influence operator_ $I$ is defined as follows. For links $i,j$, let
$I(i,j)=\frac{l_{i}^{\alpha}}{d(i,j)^{\alpha}}$ and define $I(i,i)=0$ for
simplicity of notation. The operator $I$ is additively expanded: for a set $S$
of links and a link $i$, let $I(S,i)=\sum_{j\in S}I(j,i)$ and
$I(i,S)=\sum_{j\in S}I(i,j)$. We will use the notation $I(L)=\max_{i\in
L}{I(L_{i}^{-},i)}$.

In order to identify feasible sets, we will use the following sufficient
condition for feasibility.

######  Theorem 4.

[28] For any set of links $L$ in a metric space, if $I(L)<\frac{1}{2\cdot
3^{\alpha}(4\beta+2)}$, then $L$ is feasible.

Sensitivity of Feasible Sets. A set of links is called $p$-$P$-feasible if it
is $P$-feasible with the parameter $\beta$ replaced with number $p$. The
following sensitivity argument has proved useful. It shows, in particular,
that constant factor changes to the threshold parameter $\beta$ do not affect
asymptotic results by more than a constant factor.

######  Theorem 5.

[18] Let $p$, $p^{\prime}$ be positive values, $P$ be a power assignment, and
$L$ be a $p$-$P$-feasible set. Then $L$ can be partitioned into $\left\lceil
2p^{\prime}/p\right\rceil$ sets each of which is $p^{\prime}$-$P$-feasible.

Fading Metrics. _Fading metrics_ are doubling metrics with doubling dimension
$m<\alpha$. We shall assume, without stating so explicitly, that the links are
located in a fading metric.

##  6 Capturing Feasibility with Conflict Graphs

We show that for appropriate constant $\gamma>0$ and function $f$, SINR-
feasibility is “trapped” between graph representations ${\cal G}_{\gamma}$ and
${\cal G}_{f}$; namely, each feasible set is an independent set in ${\cal
G}_{\gamma}(L)$ and each independent set in ${\cal G}_{f}(L)$ is feasible. In
particular, this holds for $f(x)=\gamma^{\prime}\widehat{\log}(x)$ for an
appropriate constant $\gamma^{\prime}>0$, where the function
$\widehat{\log}(x)$ is defined for $x\geq 1$ by
$\widehat{\log}(x)=\max(\log^{2/(\alpha-m)}(x),1)$. The gap between these
approximations is quantified using our results in Sec. 4.1, ultimately leading
to $O(\log^{*}\Delta)$ approximation for scheduling problems.

###  6.1 Independence of Feasible Sets

The theorem below is based on the simple observation that two links in the
same “highly feasible” set must be spatially separated by at least a multiple
of the length of the shorter link, implying $\gamma$-independence for some
$\gamma>0$. The constant $\gamma$ may then be adapted using Thm. 5, i.e. a
feasible set can be split into a constant number of
$\gamma^{\prime}$-independent sets for any constant $\gamma^{\prime}>0$.

######  Theorem 6.

For any constant $\gamma>0$, a $(\gamma+1)^{\alpha}$-feasible set is
$\gamma$-independent. In particular, if $\beta>1$ then each feasible set is
$(\beta^{1/\alpha}-1)$-independent.

###### Proof.

It suffices to show that two links in the same $(\gamma+1)^{\alpha}$-feasible
set must be $\gamma$-independent. Let $i,j$ be such links. Since $i,j$ are in
the same $(\gamma+1)^{\alpha}$-feasible set, the SINR condition implies that
there is a power assignment $P$ such that:

$P(i)/l_{i}^{\alpha}>(\gamma+1)^{\alpha}P(j)/d_{ji}^{\alpha}\text{ and
}P(j)/l_{j}^{\alpha}>(\gamma+1)^{\alpha}P(i)/d_{ij}^{\alpha}.$

By multiplying together the inequalities above, canceling $P(i)$ and $P(j)$
and raising to the power of $1/\alpha$, we obtain:

$d_{ij}d_{ji}>(\gamma+1)^{2}l_{i}l_{j}.$ (9)

Let us show first that $\min\\{d_{ij},d_{ji}\\}>\gamma\min\\{l_{i},l_{j}\\}$.
Indeed, if the opposite was true, e.g. if
$d_{ij}\leq\gamma\min\\{l_{i},l_{j}\\}$, the the triangle inequality would
imply that $d_{ji}\leq d_{ij}+l_{i}+l_{j}\leq(\gamma+2)\max\\{l_{i},l_{j}\\}$,
which would contradict to (9):
$d_{ij}d_{ji}\leq\gamma(\gamma+2)l_{i}l_{j}\leq(\gamma+1)^{2}l_{i}l_{j}.$

Now consider $d(s_{i},s_{j})$. Let us assume, for contradiction, that e.g.
$d(s_{i},s_{j})\leq\gamma l_{i}\leq\gamma l_{j}$. Then the triangle inequality
would imply $d_{ji}\leq d(s_{i},s_{j})+l_{i}\leq(\gamma+1)l_{i}$ and
$d_{ij}\leq d(s_{i},s_{j})+l_{j}\leq(\gamma+1)l_{j}$, which would again yield
a contradiction to (9). We prove in the same manner that
$d(r_{i},r_{j})>\gamma\min\\{l_{i},l_{j}\\}$ and conclude that
$d(i,j)>\gamma\min\\{l_{i},l_{j}\\}$, i.e., $i$ and $j$ are
$\gamma$-independent. ∎

###  6.2 Feasibility of Independent Sets

Here we show that for a large enough constant $\gamma>0$,
$\gamma\widehat{\log}$-independence implies feasibility. In particular, we
show that if a set $S$ is $\gamma\widehat{\log}$-independent then
$I(S)=O(\gamma^{m-\alpha})$. Since we assumed that $m<\alpha$, an appropriate
choice of $\gamma$ yields feasibility via Thm. 4.

The argument consists of the following stages. For any given link $i\in S$, we
first split $S_{i}^{-}$ into length classes, or _equilength subsets_ , where
each equilength subset contains links differing by at most a factor of 2 in
length. We bound the influence on link $i$ for each of those subsets
separately, and then combine those bounds using the additivity of the
influence operator $I$.

For each equilength subset $S$ the following common technique is applied:
partition the plane into concentric annuli around the link $i$, count the
number of links in each annulus and bound $I(S_{i}^{-},i)$ based on these
numbers and the fact that the links within the same annulus have almost the
same influence on link $i$ (because they are at roughly the same distance from
$i$ and have roughly similar lengths). The number of links in each annulus can
be bounded using the doubling property of the space and independence of the
links. The influence bound obtained for each subset $S$ is
$O((\gamma\widehat{\log}(l_{i}/\ell))^{m-\alpha})$, where $\ell$ is the
longest link length in $S$. The function $\widehat{\log}$ is chosen so that
combining those bounds in a sum results in an upper bound of
$I(S_{i}^{-},i)=O(\gamma^{m-\alpha})$.

We will use the following two technical observations.

######  Fact 1.

Let $\alpha\geq 1$ and $r\geq 0$ be real numbers. Then
$\frac{1}{r^{\alpha}}-\frac{1}{(r+1)^{\alpha}}\leq\frac{\alpha}{(r+1)^{\alpha+1}}.$

######  Fact 2.

Let $g(x)=\displaystyle\frac{1}{(q+x)^{\delta}}$, where $\delta>1$ and $q\geq
1$. Then $\sum_{r=0}^{\infty}{g(r)}=\displaystyle O\left(q^{1-\delta}\right).$

The following lemma bounds the influence of an equilength $1$-independent set
$S$ on a long link $i$ that is $f$-independent from the set $S$. This will be
the main building block to be used for showing that
$\gamma\widehat{\log}$-independent sets are feasible. The proof uses the
annuli argument mentioned above.

######  Lemma 2.

Let $f$ be a non-decreasing function, such that $f(x)\geq 1$ whenever $x\geq
1$. Let $S$ be an equilength $1$-independent set of links, and let $i$ be a
link s.t. for each $j\in S$, $l_{i}\geq l_{j}$ and $i$ and $j$ are
$f$-independent. Then $I(S,i)=O\left((f(l_{i}/\ell))^{m-\alpha}\right),$ where
$\ell$ denotes the longest link length in $S$.

###### Proof.

Let us denote $q=f(l_{i}/\ell)$. Note that $q\geq 1$ because $l_{i}/\ell\geq
1$.

Let us split $S$ into two subsets $S^{\prime}$ and $S^{\prime\prime}$, where
$S^{\prime}$ contains the links of $S$ that are closer to $r_{i}$ than to
$s_{i}$, i.e., $S^{\prime}=\\{j\in
S:\min\\{d(s_{j},r_{i}),d(r_{j},r_{i})\\}\leq\min\\{d(s_{j},s_{i}),d(r_{j},s_{i})\\}\\}$
and $S^{\prime\prime}=S\setminus S^{\prime}$. Let us bound $I(S^{\prime},i)$
first.

For a link $j\in S^{\prime}$, let $p_{j}$ denote the endpoint of link $j$ that
is closest to $r_{i}$, i.e., $d(i,j)=d(p_{j},r_{i})$. Consider the “chain” of
subsets $S_{1}\subseteq S_{2}\subseteq\dots\subseteq S^{\prime}$, where

$S_{r}=\\{j\in S^{\prime}:d(j,i)=d(p_{j},r_{i})\leq q\ell/2+(r-1)\ell/2\\}.$

Let $M_{r}\geq\max_{j\in S_{r}\setminus S_{r-1}}{I(j,i)}$ be some upper bound
on the maximum of $I(j,i)$ in the annulus $S_{r}\setminus S_{r-1}$ for
$r=2,3,\dots$. The value $I(S^{\prime},i)$ can be bounded as follows:

$\displaystyle I(S^{\prime},i)$ $\displaystyle=I(S_{1},i)+\sum_{r\geq
2}{\sum_{j\in S_{r}\setminus S_{r-1}}{I(j,i)}}$ $\displaystyle\leq
I(S_{1},i)+\sum_{r\geq 2}{M_{r}\cdot|S_{r}\setminus S_{r-1}|}$
$\displaystyle=I(S_{1},i)+\sum_{r\geq 2}{M_{r}(|S_{r}|-|S_{r-1}|)}$
$\displaystyle=I(S_{1},i)-|S_{1}|M_{2}+\sum_{r\geq
2}{|S_{r}|(M_{r}-M_{r+1})},$ (10)

where the last line follows by a simple rearrangement of the sum. We will next
bound the sizes of subsets $S_{r}$ and find bounds $M_{r}$.

######  Claim 1.

$S_{1}=\emptyset.$

###### Proof.

For each link $j\in S^{\prime}$, $d(p_{j},r_{i})=d(i,j)>l_{j}q\geq\ell q/2$
because $i$ and $j$ are $f$-independent and $S$ is an equilength set with
maximum link length $\ell$ and minimum link length at least $\ell/2$. ∎

######  Claim 2.

For each $r\geq 2$, $|S_{r}|\leq C\left(q+r-1\right)^{m}$, where $C$ is an
absolute constant.

###### Proof.

We bound $|S_{r}|$ using the doubling property of the metric space. Consider
any $j,k\in S_{r}$ such that $l_{j}\geq l_{k}$. By the assumption, $j,k$ are
$1$-independent; hence, $d(p_{j},p_{k})\geq
d(j,k)>\min\\{l_{j},l_{k}\\}\geq\ell/2.$ By the definition of $S_{r}$,
$d(p_{j},r_{i})\leq q\ell/2+(r-1)\ell/2$ for each $j\in S_{r}$. Because the
metric space has doubling dimension $m$, the number of points $p_{j}$ with
$j\in S_{r}$ (hence, also the size $|S_{r}|$) can be bounded as follows:

$|S_{r}|=|\\{p_{j}\\}_{j\in
S_{r}}|<C\cdot\left(\frac{q\ell/2+(r-1)\ell/2}{\ell/2}\right)^{m}=C\left(q+r-1\right)^{m}.$

∎

######  Claim 3.

Let $M_{r}=\frac{2^{\alpha}}{\left(q+r-2\right)^{\alpha}}$. For each $r\geq
2$, $\max_{j\in S_{r}\setminus S_{r-1}}\\{I(j,i)\\}<M_{r}$.

###### Proof.

For each $r>1$ and for any link $j\in S_{r}\setminus S_{r-1}$, we have that
$l_{j}\leq\ell$ and $d(i,j)>q\ell/2+(r-2)\ell/2$; hence,
$I(j,i)=\frac{l_{j}^{\alpha}}{d(i,j)^{\alpha}}<\left(\frac{\ell}{q\ell/2+(r-2)\ell/2}\right)^{\alpha}=\frac{2^{\alpha}}{\left(q+r-2\right)^{\alpha}}.$
∎

By Claim 1, the first two terms of (10) are zero. Let us fix any $r\geq 2$.
Let $M_{r}$ be as in Claim 3. By Fact 1, $M_{r}-M_{r+1}\leq\alpha
2^{\alpha}/(q+r-1)^{\alpha+1},$ and by Claim 2,

$|S_{r}|(M_{r}-M_{r+1})<\frac{C\alpha
2^{\alpha}(q+r-1)^{m}}{(q+r-1)^{\alpha+1}}=\frac{C\alpha
2^{\alpha}}{(q+r-1)^{\alpha-m+1}}.$

By plugging these inequalities into (10) and using Fact 2, we get the desired
bound for $I(S^{\prime},i)$:

$\displaystyle I(S^{\prime},i)<\sum_{r\geq 2}{|S_{r}|(M_{r}-M_{r+1})}<C\alpha
2^{\alpha}\sum_{r\geq 2}{\frac{1}{(q+r-1)^{\alpha-m+1}}}\in O(q^{m-\alpha}).$

The proof holds symmetrically for the set $S^{\prime\prime}$. Recall that
$S^{\prime\prime}$ consists of the links of $S$ that are closer to the sender
$s_{i}$ than to the receiver $r_{i}$. Now, we can define the set
$\\{p_{j}\\}_{j\in S^{\prime\prime}}$ where $p_{j}$ is the endpoint of link
$j$ that is closest to $r_{i}$, for each $j\in S^{\prime\prime}$. The rest of
the proof will be identical, by replacing $r_{i}$ with $s_{i}$ in the
formulas. ∎

Having a bound for the influence of each equilength set, we can now split the
whole set into equilength subsets (length classes), bound the influence of
each equilength subset using Lemma 2 and combine them into a series that
converges when we choose $f(x)=\gamma\widehat{\log}(x)$.

######  Theorem 7.

Let $L$ be a $\gamma\widehat{\log}$-independent set with $\gamma\geq 1$. Then
$I(L)=O\left(\gamma^{m-\alpha}\right).$

###### Proof.

Let us fix an arbitrary link $i\in L$. We have for each $j\in L_{i}^{-}$,
$d(i,j)>\gamma l_{j}\widehat{\log}(l_{i}/l_{j})$ because of
$\gamma\widehat{\log}$-independence and that $l_{i}\geq l_{j}$. Let $\ell_{0}$
denote the minimum link length in $L_{i}^{-}$. We partition $L_{i}^{-}$ into
at most $\lceil\log{l_{i}/\ell_{0}}\rceil$ equilength subsets
$L_{1},L_{2},\dots$ as follows:

$L_{t}=\\{j\in L_{i}^{-}:2^{t-1}\ell_{0}\leq l_{j}<2^{t}\ell_{0}\\},$

for $t=1,2,\dots$. Let $\ell_{t}$ be the longest link length in $L_{t}$. The
conditions of Lemma 2 hold for each $L_{t}$: it is an equilength
$1$-independent set ($\gamma\widehat{\log}$-independence implies
$1$-independence for $\gamma\geq 1$) and is $f$-independent from link $i$,
with $f=\gamma\widehat{\log}$. Note also that $f(x)\geq 1$ when $x\geq 1$.
Applying the lemma, we obtain

$I(L_{t},i)=O\left((\gamma\widehat{\log}(l_{i}/\ell_{t}))^{m-\alpha}\right).$

Let $d$ denote the largest index $t$ for which $L_{t}$ is not empty. By the
definition of function $\widehat{\log}$ we have that
$\widehat{\log}(l_{i}/\ell_{d})\geq 1$ and for each $t<d$,
$\widehat{\log}(l_{i}/\ell_{t})=\log^{2/(\alpha-m)}(l_{i}/\ell_{t})\geq(d-t)^{2/(\alpha-m)}$.
Thus,

$I(L_{i}^{-},i)=\sum_{t=1}^{d}{I(L_{t},i)}\leq
c\gamma^{m-\alpha}\left(1+\sum_{t=1}^{d}{\left((d-t)^{2/(\alpha-m)}\right)^{m-\alpha}}\right)=O(\gamma^{m-\alpha}),$

where $c$ is a constant. Since this holds for arbitrary $i\in L$, we have that
$I(L)=O(\gamma^{m-\alpha})$. ∎

Since the theorem above holds for any $\gamma\geq 1$, we obtain the desired
result.

######  Corollary 1.

There is a constant $\gamma\geq 1$ such that each
$\gamma\widehat{\log}$-independent set is feasible.

##  7 Implications

###  7.1 Scheduling and WCapacity Approximation

Using our method of capturing feasibility with graphs, we approximate
Scheduling and WCapacity problems within a factor of $O(\log^{*}{\Delta})$.
Let us first formally define the problems and related terms.

A _schedule_ for a set $L$ of links is a partition of $L$ into feasible
subsets (or _slots_). The _length_ of the schedule is its number of slots. The
Scheduling _problem_ is to find a minimum length schedule for a given set $L$.
The length of an optimal schedule for $L$ is denoted $OPTS(L)$.

The WCapacity problem is the generalized dual of Scheduling, where given a set
$L$ of links with weights $\omega:L\rightarrow\mathbb{R}^{+}$, the goal is to
find a feasible subset $S\subseteq L$ of maximum weight $\sum_{i\in
S}{\omega(i)}$.

######  Theorem 8.

There are polynomial $O(\log^{*}{\Delta})$-approximation algorithms for
Scheduling and WCapacity. The approximation is obtained by coloring the graph
${\cal G}_{\gamma\widehat{\log}}$ (for an appropriate constant $\gamma\geq 1$)
in the case of Scheduling and by approximating its maximum weighted
independent set in the case of WCapacity.

###### Proof.

First consider the Scheduling problem. Let $L$ be an input to Scheduling. We
construct and color the graph ${\cal G}_{\gamma\widehat{\log}}(L)$ with
constant $\gamma$ chosen as in Corollary 1. By Corollary 1, such a coloring
corresponds to a feasible schedule.

To derive the approximation factor, observe on one hand that in view of Thms.
5 and 6, any schedule of $L$ can be refined into a coloring of ${\cal
G}_{\gamma}(L)$ with only constant factor increase in the number of slots.
Thus, $OPTS(L)=\Omega(\chi({\cal G}_{\gamma}(L)))$. On the other hand, by Thm.
1, $\chi({\cal
G}_{\gamma\widehat{\log}}(L))=O(\widehat{\log}^{*}(\Delta))\cdot\chi({\cal
G}_{\gamma}(L))=O(\log^{*}{\Delta})\cdot OPTS(L)$. It is readily verified that
the function $\gamma\widehat{\log}$ is strongly sub-linear, implying, via Thm.
3, that ${\cal G}_{\gamma\widehat{\log}}(L)$ is constant-simplicial and thus
colorable within constant approximation factor.

Now consider the WCapacity problem. Let a set $L$ be given. As in the case of
Scheduling, we first construct the graph ${\cal G}_{\gamma\widehat{\log}}(L)$
with constant $\gamma$ chosen as in Corollary 1. We find a constant-factor
approximate weighted maximum independent set in ${\cal
G}_{\gamma\widehat{\log}}(L)$ using the fact that this graph is constant-
simplicial. By Corollary 1, the resulting set is feasible, i.e. it is a valid
solution for WCapacity. Now let us derive the approximation factor. Let
$W_{l}$ and $W_{u}$ be the weights of the weighted maximum independent sets in
${\cal G}_{\gamma}(L)$ and ${\cal G}_{\gamma\widehat{\log}}(L)$ respectively,
and let $W_{o}$ be the weight of the optimal solution to WCapacity in $L$. Let
$S$ be a solution to WCapacity in $L$. Since $S$ is feasible, it can be split
into a constant number of $\gamma$-independent subsets, by Thms. 5 and 6. Let
$S^{\prime}$ be the largest weight subset. Obviously, the weight of
$S^{\prime}$ is $\Omega(W_{o})$, implying that $W_{l}=\Omega(W_{o})$, as
$S^{\prime}$ is an independent set in ${\cal G}_{\gamma}$. On the other hand,
Thm. 1 implies that $S^{\prime}$ can be refined into at most
$O(\log^{*}{\Delta})$ $\gamma\widehat{\log}$-independent subsets. The largest
weight subset will have weight at least $\Omega(W_{l}/\log^{*}{\Delta})$,
which implies that
$W_{u}=\Omega(W_{l}/\log^{*}{\Delta})=\Omega(W_{o}/\log^{*}{\Delta})$. ∎

###  7.2 Measure of Interference

While approximation algorithms give bounds relative to an optimal value, it is
frequently advantageous to have bounds in terms of some intrinsic parameters
or more easily computable properties. Thus the interest in bounding chromatic
numbers of graphs in terms of clique numbers, broadcast algorithms in terms of
network diameter, and routing time in terms of “congestion + dilation”. Our
results also imply bounds for the optimum schedule length that can be
efficiently computed from the network topology. Previous such results involved
logarithmic factors in $n$ and/or $\Delta$ [9, 31].

Let $G$ be a $k$-simplicial graph and let $v_{1},v_{2},\dots,v_{n}$ be a
$k$-simplicial elimination order of vertices, which for our conflict graphs is
by increasing link length. A $k$-approximate coloring of $G$ is obtained by
coloring the vertices greedily in reverse order. The number of colors used is
at most the maximum post-degree plus 1, or
$\max_{i}\\{|N(v_{i})\cap\\{v_{i+1},\dots,v_{n}\\}|\\}+1\leq k\cdot\chi(G)+1$.
We therefore define

$B_{f}(L)=\max_{i\in L}|\\{j\in L:l_{j}\geq l_{i},d(i,j)\leq
l_{i}f(l_{j}/l_{i})\\}|,$

for a function $f$, and observe that $\chi({\cal G}_{f}(L))=\Theta(B_{f}(L))$.
The results of Sec. 6 and 8 then imply the following theorem.

######  Theorem 9.

There are constants $a,b>0$ and $\gamma\geq 1$, such that for any set $L$,

$a\cdot B_{\gamma}(L)\leq OPTS(L)\leq b\cdot B_{\widehat{\log}}(L)\text{ and
}\frac{B_{\widehat{\log}}(L)}{B_{\gamma}(L)}=O(\log^{*}{\Delta(L)}).$

Moreover, there are infinitely many instances $L^{\prime}$ and
$L^{\prime\prime}$ s.t.
$\frac{OPTS(L^{\prime})}{B_{\gamma}(L^{\prime})}=\Omega(\log^{*}{\Delta(L^{\prime})})$
and
$\frac{B_{\widehat{\log}}(L^{\prime\prime})}{OPTS(L^{\prime\prime})}=\Omega(\log^{*}{\Delta(L^{\prime\prime})})$.

###  7.3 A Necessary and Sufficient Condition for Feasibility

Another interesting implication of Thm. 7 is the following result that shows
that the sufficient condition for feasibility stated in Thm. 4 is essentially
necessary in doubling metric spaces. This result is of independent interest,
as it may prove useful for improved analysis of various problems. It should be
noted that this theorem does not hold in general metric spaces.

The proof consists of two parts, bounding the influence on a link $i$ by
faraway links (i.e., links that are highly independent from link $i$) on one
hand using Thm. 7, and by near links (the rest) on the other hand, using
simple manipulations of the SINR condition.

######  Theorem 10.

Let $L$ be a $3^{\alpha}$-feasible set of links. Then, $I(L)=O(1).$

###### Proof.

Let us fix a link $i\in L$ and denote $S=L_{i}^{-}$. We split $S$ into two
subsets $S_{1}$ and $S_{2}$, where for each link $j\in S_{1}$, $j$ and $i$ are
$f$-independent with $f(x)=2x$, and $S_{2}=S\setminus S_{1}$.

Recall that by Thm. 6, $3^{\alpha}$-feasibility implies $2$-independence of
$S_{1}$. The bound $I(S_{1},i)=O(1)$ then follows by applying an analogue of
Thm. 7 with $\gamma=1$ and with $f$-independence instead of
$\widehat{\log}$-independence, which can be done because
$\widehat{\log}(x)=O(f(x))$.

It remains to show that $I(S_{2},i)=O(1)$. Let $P$ be a power assignment for
which $L$ is $P$-feasible. Then, the SINR condition gives us the following
inequalities:

$\frac{P(i)}{l_{i}^{\alpha}}>3^{\alpha}\sum_{j\in
S_{2}}{\frac{P(j)}{d_{ji}^{\alpha}}},\mbox{ and
}\frac{P(j)}{l_{j}^{\alpha}}>3^{\alpha}\frac{P(i)}{d_{ij}^{\alpha}}\mbox{ for
all }j\in S_{2}.$

By replacing $P(j)$ with
$3^{\alpha}\frac{P(i)l_{j}^{\alpha}}{d_{ij}^{\alpha}}$ in the first inequality
and simplifying the expression, we get:

$\sum_{j\in
S_{2}}\frac{l_{i}^{\alpha}l_{j}^{\alpha}}{d_{ij}^{\alpha}d_{ji}^{\alpha}}\leq
9^{-\alpha}.$ (11)

In order to extract a bound on $I(S_{2},i)$ from (11), we will show that one
of the values $d_{ij}^{\alpha},d_{ji}^{\alpha}$ in the denominator can be
canceled out with $l_{i}^{\alpha}$ in the numerator and the other one can be
replaced with $d(i,j)^{\alpha}$ by only introducing additional constant
factors in the expression. Such a modification will transform the left side of
(11) into $I(S_{2},i)$.

Let us assume w.l.o.g. that $d_{ij}\geq d_{ji}$. Recall that for each $j\in
S_{2}$, $d(i,j)\leq 2l_{i}$ by definition of $S_{2}$. Using the triangle
inequality, we obtain $d_{ij}\leq d(i,j)+l_{i}+l_{j}\leq 4l_{i}$. On the other
hand, as it was mentioned above, the set $S_{2}$ is $2$-independent, which
implies that $d_{ji}\geq d(i,j)>2l_{j}$. Using the triangle inequality again,
we obtain:

$d(s_{i},s_{j})\geq d_{ij}-l_{j}\geq d_{ji}-l_{j}>d_{ji}/2\text{ and
}d(r_{i},r_{j})\geq d_{ji}-l_{j}>d_{ji}/2.$

Thus, $d(i,j)>d_{ji}/2$. By replacing $d_{ij}$ with $4l_{i}$ and $d_{ji}$ with
$2d(i,j)$ in the left-hand part of (11), we obtain the desired bound:
$I(S_{2},i)\leq(8/9)^{\alpha}$. Since this holds for an arbitrary $i\in L$, we
get that $I(L)=O(1)$. ∎

_Remark._ Note that Thm. 5 implies that any feasible set can be refined into a
constant number of $3^{\alpha}$-feasible subsets. Thus, the influence function
fully captures feasibility in fading metrics, modulo constant factors.

##  8 Limitations of the Graph-Based Approach

We have found that conflict graphs can achieve a remarkably good, yet super-
constant, approximation for scheduling problems in doubling metrics. We
examine in this section how far this approach can be pushed, obtaining
essentially tight bounds. We treat these issues in terms of the Scheduling
problem.

In the first part of the section, we expose the limitations of the graph
method in Euclidean spaces. We show, in particular, that conflict graphs do
not yield any non-trivial approximation to the Scheduling problem in terms of
the number of links $n$. In particular, they cannot lead to constant factor
approximation. We also consider approximation limits in terms of the parameter
$\Delta$, and show that for all reasonable functions $f$, the approximation
factor is at least $\Omega(\log^{*}{\Delta})$. Thus, the approximation factor
we obtained cannot be improved within a conflict-graph framework. Note that
the instances we construct are embedded on the real line, i.e., in one
dimensional space.

In the second part of the section, we find that the graph method cannot
provide any non-trivial approximation guarantees in general metric spaces,
neither in terms of $n$ nor $\Delta$.

###  8.1 Euclidean Spaces

In the following theorem, we construct, for any function $f=\omega(1)$, a
feasible set of $f$-adjacent links. The construction is based on the following
observations. On the one hand, it follows from Thm. 4 that any set of
exponentially growing links arranged sequentially by the order of length on
the real line is (almost) feasible. On the other hand, given such a set $S$ of
links on the line, a new link $j$ can be formed so that $j$ is $f$-adjacent to
all the links in $S$ while the set $S\cup j$ stays feasible; the only
requirement is that $j$ be long enough. Our construction then builds
recursively on these ideas.

######  Theorem 11.

Let $f(x)=\omega(1)$. For any integer $n>0$, there is a _feasible_ set $L$ of
$n$ links arranged on the real line, such that ${\cal G}_{f}(L)$ is a clique,
i.e., $\chi({\cal G}_{f}(L))=n$. Moreover, if $f(x)\geq g(x)$ ($x\geq 1$) for
a strongly sub-linear increasing function $g(x)$ with $g(x)=\omega(1)$, then
$n=\Omega(g^{*}(\Delta))$.

###### Proof.

Consider a set of $cn$ links $\\{1,2,\dots,cn\\}$ arranged sequentially from
left to right on the real line, where $c>0$ is a constant to be chosen later.
Each link $i$ is directed from left to right and for each $i=1,2,3,\dots,n-1$,
the nodes $s_{i+1}$ and $r_{i}$ share the same location on the line, i.e.,
$r_{i}=s_{i}+l_{i}=s_{i+1}$. See Figure 1. The lengths of links are defined
inductively, as follows. We set $l_{1}=1$, and for $i\geq 1$, we choose
$l_{i+1}$ to be the minimum value satisfying:

$\displaystyle l_{i+1}$ $\displaystyle\geq 2l_{i}$ (12) $\displaystyle
2d(i+1,j)=2d_{i+1,j}$ $\displaystyle\leq l_{j}f(l_{i+1}/l_{j})\mbox{ for all
}j\leq i.$ (13)

Such a value of $l_{i+1}$ can be chosen as follows. By the inductive
hypothesis, we have $l_{j}\geq 2l_{j-1}$ for $j=2,3,\dots,i$. This implies
that $l_{i}\geq\sum_{j=1}^{i-1}{l_{j}}$. Then, we have that
$d_{i+1,j}=\sum_{t=j+1}^{i}{l_{t}}\leq 2l_{i}$ for $j=1,2,\dots,i$. Thus, it
is enough to choose $l_{i+1}$ so that $l_{i+1}\geq 2l_{i}$ and $4l_{i}\leq
l_{j}f(l_{i+1}/l_{j})$, which can be done using $f=\omega(1)$ and the fact
that the values of $l_{j}$ for $j=1,2,\dots,i$ are already fixed at this
point. This completes the construction.

Figure 1: The construction in Thm. 11.

First note that (13) implies that ${\cal G}_{f}(L)$ is a clique. It remains to
argue feasibility. Consider the odd numbered links
$S=\\{1,3,\dots,...,2t+1\\}$. Let us fix a link $2k+1\in S$. Note that for
each $j\in S_{2k+1}^{-}$, $d(j,2k+1)\geq l_{2k}$. We have that

$I(S_{2k+1}^{-},2k+1)=\sum_{j\in
S_{2k+1}^{-}}{\frac{l_{j}^{\alpha}}{d(j,2k+1)^{\alpha}}}\leq\sum_{j\in
S_{2k+1}^{-}}{\left(\frac{l_{j}}{l_{2k}}\right)^{\alpha}}\leq\sum_{j\in
S_{2k+1}^{-}}{\frac{l_{j}}{l_{2k}}}\leq 1,$

where the second inequality holds because $l_{j}/l_{2k}\leq 1$ and the last
inequality follows from (12). Thus, we can extract a constant fraction
$S^{\prime}$ of $S$ that is feasible, using Thm. 5. With the right choice of
the constant $c$ in the beginning of the proof we have that $|S^{\prime}|=n$.
This proves the first part of the theorem.

Now let us assume that $f(x)\geq g(x)$ for a strongly sub-linear function
$g(x)$ with $g(x)=\omega(1)$. Then, there is a constant $x_{0}$ such that
$g(x)<x$ for all $x\geq x_{0}$ (because $g(x)=o(x)$) and there is a constant
$c$ such that $2g(x)/x\leq g(y)/y$ whenever $x\geq cy$ (strong sub-linearity).
In this case we repeat the construction above with slight modifications.

We set $l_{1}=1$ and set $l_{i+1}>\max\\{c,x_{0}\\}$ be the minimum value s.t.
$g(l_{i+1})\geq 2l_{i}$, for $i=1,2,\dots$ (such a value exists because
$g(x)=\omega(1)$). Let us show that the conditions (12-13) hold with these
lengths.

Since $l_{i+1}\geq x_{0}$, we have that $l_{i+1}>g(l_{i+1})\geq 2l_{i}$, which
implies (12). This in turn implies, as observed in the first part of the
proof, that $d(i+1,j)<2l_{i}$ for all $2\leq j\leq i$. Let us denote
$x=l_{i+1}/l_{1}=l_{i+1}$ and $y=l_{i+1}/l_{j}$. Note that $x/y=l_{j}\geq c$,
so we have, by strong sub-linearity of $g$, that $g(y)/y\geq 2g(x)/x$, or
equivalently, that $l_{j}\cdot g(l_{i+1}/l_{j})\geq 2\cdot g(l_{i+1})$; hence
$l_{j}\cdot g(l_{i+1}/l_{j})\geq 4l_{i}>2d(i+1,j)$ for all $2\leq j\leq i$,
which means that (13) also holds.

It remains to prove the lower bound for $n$. Recall that the value of
$l_{i+1}$ is the minimum satisfying $g(l_{i+1})\geq 2l_{i}$ for
$i=1,2,\dots,n-1$. Then, we have $g(l_{i+1}/2)<2l_{i}$ or, equivalently,
$h(l_{i+1}/2)<l_{i}/2$, where $h(x)=g(x)/4$. Thus,

$1/2=l_{1}/2>h(l_{2}/2)>h(h(l_{3}/2))>\dots>h^{(n-1)}(l_{n}/2)=h^{(n-1)}(\Delta/2),$

which implies that $n=\Omega(h^{*}(\Delta/2))=\Omega(g^{*}(\Delta))$. ∎

######  Corollary 2.

In terms of the number of links $n$, the approximation factor for Scheduling
when using ${\cal G}_{f}$ with any $f=\omega(1)$ is no better than $n$.

By choosing $g(x)=\gamma\widehat{\log}(x)$ in Thm. 11, we obtain that the
approximation factor of $O(\log^{*}{\Delta})$ cannot be improved for ${\cal
G}_{\gamma\widehat{\log}}$.

######  Corollary 3.

Let $f(x)=\Omega(\log^{(c)}x)$ for a constant $c$. Then, for each $\Delta>0$,
there is a _feasible_ set of links $L$ with $\Delta(L)=\Omega(\Delta)$, such
that ${\cal G}_{f}(L)$ is a clique of size $\Theta(\log^{*}{\Delta(L)})$.

While the theorem above shows that graphs ${\cal G}_{f}$ with
$f=\Omega(\log^{(c)}x)$ for some constant $c$ require too much separation, the
theorem below shows that graphs ${\cal G}_{f}$ with $f=O(\log^{1/\alpha}x)$
provide insufficient separation, leading, perhaps surprisingly, to a similar
sized gap of $\log^{*}{\Delta}$. Namely, $\chi({\cal
G}_{f}(L^{\prime}))=\frac{OPTS(L^{\prime})}{\Omega(\log^{*}{\Delta})}$ holds
for certain instances $L^{\prime}$. The construction follows the general
structure of Thm. 7 in [20] of a lower bound for scheduling the edges of a
minimum spanning tree of a set of points in the plane. There are two technical
challenges to overcome, in order to implement this structure in our setting.
First, the construction of [20] is not $f$-independent. Second, even when
ignoring the $f$-independence requirement, the lower bound for the scheduling
number obtained in [20] is only $\Omega(\log{\log^{*}{\Delta}})$.

######  Theorem 12.

Let $f(x)=O(\log^{1/\alpha}x)$. For each $\Delta>0$, there is an
$f$-independent set of links $L$ on the real line with
$\Delta(L)=\Omega(\Delta)$ that cannot be scheduled in fewer than
$\Theta(\log^{*}{\Delta(L)})$ slots.

We describe the idea of the construction informally. The construction is
inductive, starting from a trivial instance $L_{1}$ containing a single link.
For $t\geq 1$, assume there is an instance $L_{t}$ having the desired
properties, i.e., $L_{t}$ is $f$-independent and with $OPTS(L)\geq t$. In
order to construct the instance $L_{t+1}$, consider a single link $j$ that is
longer than the links in $L_{t}$ and place it at distance $d$ from $L_{t}$ so
that all the links in $L_{t}$ are $f$-independent from $j$. Let $I_{0}$ denote
the minimum influence of a link from $L_{t}$ on link $j$. Now, take $k$
identical copies of $L_{t}$ and place them at a distance $d$ from $j$. This
will of course violate the independence between different instances, which we
will address shortly, but they will still be independent from link $j$. The
idea is that if the number of copies $k$ is large enough, then for any set $S$
containing at least one link from each copy, we will have
$I(S,j)=kI_{0}>c_{0}$, where $c_{0}$ is a constant large enough to ensure that
$S\cup\\{j\\}$ is infeasible (based on Thm. 10). This will mean that any
schedule of the link $j$ and the $k$ copies must place at least _one whole
copy_ of $L_{t}$ in slots separate from $j$. Since it takes at least $t$ slots
to schedule one copy of $L_{t}$, it takes at least $t+1$ slots to schedule all
the copies together with link $j$.

It remains to address the issue of $f$-independence between different copies.
Note that because of the scale-invariance of the influence operator, we can
scale a copy of $L_{t}$ by a factor $s$ and place it further than before, at a
distance $s\cdot d$ from link $j$ and still have the minimum influence of
$I_{0}$ on $j$. However, in order for this influence to be taken into the
account, the link $j$ must still be longer than the links in the scaled
instance. Using this trick, we can scale different copies by different factors
and guarantee their mutual independence, while preserving the properties we
had in the case of identical copies. Since the link lengths must grow
exponentially at each step $t$, the number $t$ of slots required will be small
compared to the number of links and the parameter $\Delta$, but will still be
$\Omega(\log^{*}{\Delta})$.

###### Proof.

For a set $S$ of links, we will use $diam(S)$ to denote the diameter of $S$,
or the maximum distance between nodes in $S$.

We will construct a set of links that cannot be scheduled in fewer than
$\Theta(\log^{*}{\Delta})$ $3^{\alpha}$-feasible slots, relying on the
necessary condition for feasibility (Thm. 10). This will be sufficient to
prove the theorem, as Thm. 5 will imply that there cannot exist a
$\beta$-feasible schedule with $\Theta(\log^{*}{\Delta})$ slots for that set,
for any constant $\beta$.

Let us fix a function $f$. Note that since $f=O(\log^{1/\alpha})$, there is a
constant $C\geq 1$ s.t. $f(x)\leq C\log^{1/\alpha}x$. We construct sets
$L_{t}$ of links recursively. The construction is illustrated in Figure 2. All
the links will be arranged on the real line and the receiver of each link will
be to the right of the sender. Initially, we have a set $L_{1}$ consisting of
a single link of length $1$, for which a single slot is sufficient and
necessary. Suppose that we have already constructed $L_{t}$ with the property
that at least $t$ slots are required for scheduling $L_{t}$. The instance
$L_{t+1}$ is constructed as follows using $k$ scaled copies of $L_{t}$, where
$k$ is to be determined. First we place a single very long link $j_{t+1}$ in
the line. We then add, in order from left to right, copies
$L_{t}^{1},L_{t}^{2},\dots,L_{t}^{k}$ of $L_{t}$ to the right of $j_{t+1}$,
where $L_{t}^{s}$ is the copy of $L_{t}$ scaled by a factor $8^{s}$. The idea
is to make the construction so that the following properties hold:

  1. (i)

$L_{t+1}$ is $f$-independent,

  2. (ii)

$t=\Omega(\log^{*}{\Delta(L_{t})})$,

  3. (iii)

for any set $S=\\{i_{1},i_{2},\dots,i_{k}\\}$ with $i_{s}\in L_{t}^{s}$,
$s=1,2,\dots,k$, we have that$I(S,j_{t+1})>c_{0}$ for a constant $c_{0}$ of
our choice.

The last property ensures that each $3^{\alpha}$-feasible schedule of
$L_{t+1}$ must put a whole copy $L_{t}^{s}$ in a slot separate from $j_{t+1}$.
Indeed, if there was a schedule that placed at least one link from each copy
$L_{t}^{s}$ in the same slot with $j_{t+1}$ then we would get a contradiction
with (iii): we would have $I(S,j_{t+1})=O(1)$ for some $S$ as above, due to
Thm. 10. Recall that $L_{t}$ needs at least $t$ slots to be scheduled, and so
does each copy of it. It follows that $L_{t+1}$ needs at least
$t+1=\Omega(\log^{*}{\Delta(L_{t})})$ slots to be scheduled, one for $j_{t}$
and at least $t$ for scheduling the copies of $L_{t}$. Proving the properties
(i-iii) will complete the proof of the theorem.

Figure 2: The recursive construction of $L_{t+1}$.

Now let us describe the inductive step of the construction in detail. Let
$\ell_{t}=diam(L_{t})$ denote the diameter of $L_{t}$. The number of copies of
$L_{t}$ is $k=2^{c\ell_{t}}$ for a large enough constant $c$. The length of
link $j_{t+1}$ is set to $l_{j_{t+1}}=8^{k+1}\ell_{t}$. It remains to specify
the placement of each copy $L_{t}^{s}$ so as to guarantee the desired
properties of $L_{t+1}$.

We assume by induction that the links within each copy of $L_{t}$ are
$f$-independent. We place the copies $L_{t}^{s}$ so that the links between any
two copies are $f$-independent and are $f$-independent from $j_{t+1}$. Let
$\ell_{t}^{s}=diam(L_{t}^{s})=8^{s}\ell_{t}$ denote the diameter of
$L_{t}^{s}$. Let $g(x)=C\log^{1/\alpha}x$. We place each copy $L_{t}^{s}$ at a
distance $d(L_{t}^{s},j_{t+1})=2\ell_{t}^{s}g(l_{j_{t+1}}/\ell_{t}^{s})$ from
$j_{t+1}$. The construction is ready.

We first prove the property (i).

######  Claim 4.

With the distances defined as above, the set $L_{t+1}$ is $f$-independent.

###### Proof.

Consider any link $i\in L_{t}^{s}$. We have that

$d(i,j_{t+1})\geq
d(L_{t}^{s},j_{t+1})=2\ell_{t}^{s}g(l_{j_{t+1}}/\ell_{t}^{s})\geq
2l_{i}g(l_{j_{t+1}}/l_{i})\geq 2l_{i}f(l_{j_{t+1}}/l_{i}),$

where the second inequality follows from the fact that $xg(c/x)$ is an
increasing function of $x$ and that $l_{i}<\ell_{t}^{s}$, and the third
inequality follows because $f(x)\leq g(x)$ for all $x$. Thus, all the links in
$L_{t}^{s}$ are $f$-independent from $j_{t+1}$. Now let us show that any two
links $i,k$ with $l_{i}\leq l_{k}$ from different copies $L_{t}^{s}$ and
$L_{t}^{r}$ with $s>r$ are $f$-independent (no matter which link is from which
copy). Since $f(x)\leq g(x)$, it will be enough to show that

$d(i,k)>l_{i}g(l_{k}/l_{i}).$ (14)

Recall that $xg(c/x)$ is an increasing function of $x$. Then, for a fixed $k$,
the right side of (14) is maximized when $l_{i}$ is maximum. On the other
hand, for a fixed $i$, the value $g(l_{k}/l_{i})$ is maximized when $l_{k}$ is
maximum, because $g$ is an increasing function. Let $j_{t}$ denote the maximum
length link in $L_{t}$. Then, the maximum link length in $L_{t}^{s}$ (in
$L_{t}^{r}$) is $8^{s}l_{j_{t}}$ ($8^{r}l_{j_{t}}$). Therefore, it is enough
to show that

$d(i,k)>\ell_{t}^{r}g(8^{s}l_{j_{t}}/(8^{r}l_{j_{t}}))=\ell_{t}^{r}g(8^{s-r})=C(3(s-r))^{1/\alpha}\ell_{t}^{r}.$

We have that

$d(i,k)\geq
d(L_{t}^{s},L_{t}^{r})=d(L_{t}^{s},j_{t+1})-d(L_{t}^{r},j_{t+1})-\ell_{t}^{r}\geq
2\ell_{t}^{s}g(l_{j_{t+1}}/\ell_{t}^{s})-3\ell_{t}^{r}g(l_{j_{t+1}}/\ell_{t}^{r}).$

The term $g(l_{j_{t+1}}/\ell_{t}^{r})$ can be bounded by

$g(l_{j_{t+1}}/\ell_{t}^{r})=g(8^{s-r}l_{j_{t+1}}/\ell_{t}^{s})\leq
3^{s-r}g(l_{j_{t+1}}/\ell_{t}^{s}),$

where the last inequality follows because $g(8x)\leq 3g(x)$ for $x\geq 2$
(note that $\alpha\geq 1$). Thus,

$d(i,k)\geq
2\ell_{t}^{s}g(l_{j_{t+1}}/\ell_{t}^{s})-3^{s-r+1}\ell_{t}^{r}g(l_{j_{t+1}}/\ell_{t}^{s})>C(2\cdot
8^{s-r}-3\cdot 3^{s-r})\ell_{t}^{r}>C(3(s-r))^{1/\alpha}\ell_{t}^{r}.$

∎

Next, we can observe that (the first line follows because the links are
arranged linearly)

$\displaystyle\ell_{t+1}$
$\displaystyle=l_{j_{t+1}}+d(L_{t}^{k},j_{t+1})+\ell_{t}^{k}$
$\displaystyle\leq
l_{j_{t+1}}+2\ell_{t}^{k}g(l_{j_{t+1}}/\ell_{t}^{k})+\ell_{t}^{k}$
$\displaystyle=8^{k+1}\ell_{t}+8^{k}\ell_{t}g(8)+8^{k}\ell_{t}$
$\displaystyle=O(8^{2^{c\ell_{t}}}).$ (15)

Since the minimum link-length in $L_{t+1}$ is $1$, we can conclude that
$\Delta(L_{t})<\ell_{t}\leq 2\uparrow(c_{1}t)$ for a constant $c_{1}$ and for
each $t$, where $\uparrow$ denotes the tower function. This implies that
$t=\Omega(\log^{*}{\Delta(L_{t})})$. The property (ii) is now proven.

It remains to check that (iii) holds. Let us consider a link $i_{s}$ from
$L_{t}^{s}$ where $i_{s}$ is the copy of link $i$ in $L_{t}$. We have that

$d(i_{s},j_{t})\leq\ell_{t}^{s}+d(L_{t}^{s},j_{t})=\ell_{t}^{s}+2C\ell_{t}^{s}\log^{1/\alpha}{(l_{j_{t+1}}/\ell_{t}^{s})}\leq
c_{2}\ell_{t}^{s}(k-s+1)^{1/\alpha},$

for a constant $c_{2}$. This implies:

$I(i_{s},j_{t+1})=\left(\frac{l_{i_{s}}}{d(i_{s},j_{t+1})}\right)^{\alpha}\geq\left(\frac{l_{i_{s}}}{c_{2}(k-s+1)^{1/\alpha}\ell_{t}^{s}}\right)^{\alpha}\geq\frac{1}{c_{3}(k-s)\ell_{t-1}},$

where we used the fact that $l_{i_{s}}/\ell_{t}^{s}=l_{i}/\ell_{t}\geq
1/\ell_{t}$. Now, let $i_{s},$ $s=1,2,\dots,k$ be a set of links where
$i_{s}\in L_{t}^{s}$ and they are not necessarily the copies of the same link
of $L_{t}$. Then,

$I(S,j_{t+1})=\sum_{s=1}^{k}I(i_{s},j_{t+1})>\sum_{1}^{k}{\frac{1}{c_{3}(k-s+1)\ell_{t}}}=\Omega\left(\frac{\log{k}}{\ell_{t}}\right).$

Recall that $k=2^{c\ell_{t}}$. By taking the constant $c$ large enough, we can
thus guarantee the property (iii). This completes the proof of all the
properties of $L_{t}$ and the proof of the theorem. ∎

###  8.2 General Metric Spaces

The following theorem shows that conflict graphs can be arbitrarily far from
schedules in general metric spaces. Given a function $f$, the construction
consists of an $f$-independent set of _unit length_ links. Since all links
have length $1$, $f$-independence is equivalent to $f(1)$-independence. The
separation between the links is just enough to ensure $f(1)$-independence.
However, since all the links are equally ($f(1)$-) separated from any given
link, their interference accumulates and only a constant number of links can
be scheduled in the same slot. This leads to schedules of length $\Theta(n)$.

######  Proposition 3.

For each function $f$ and any $n\geq 1$, there is an $f$-independent set of
$n$ unit length links (hence, $\Delta=1$) that cannot be scheduled into less
than $\Theta(n)$ slots.

###### Proof.

Let $L=\\{1,2,\dots,n\\}$ be the set of links. We define the lengths and the
distances between the links such as to ensure the metric constraints hold. For
each link $i$ we define $l_{i}=1$. The distances between the nodes are defined
as follows:

  * ✓

sender to sender: $d(s_{i},s_{j})=f(1)\cdot(l_{i}+l_{j})=2f(1)$,

  * ✓

sender to receiver: $d(s_{i},r_{j})=d(s_{i},s_{j})+l_{j}=2f(1)+1$,

  * ✓

receiver to receiver: $d(r_{i},r_{j})=d(s_{i},s_{j})+l_{i}+l_{j}=2f(1)+2$.

It is straightforward to check that such distances define a metric. Moreover,
the whole set of links in this metric is $f$-independent, since
$d(i,j)>f(1)\cdot l_{i}=l_{i}f(l_{j}/l_{i})$. Let us consider any $P$-feasible
subset $S$ of $k$ links for a power assignment $P$. Let us fix a link $i\in
S$. The SINR condition implies: $P(i)>\beta\sum_{j\in
S\setminus\\{i\\}}\frac{P(j)l_{i}^{\alpha}}{d_{ji}^{\alpha}}$ and
$P(j)>\beta\frac{P(i)l_{j}^{\alpha}}{d_{ij}^{\alpha}}$ for all $j\in
S\setminus\\{i\\}$. By replacing $P(j)$ with $\frac{\beta
P(i)l_{j}^{\alpha}}{d_{ij}^{\alpha}}$ in the first inequality and canceling
the term $P(i)$, we obtain:

$1>\beta^{2}\sum_{j\in
S\setminus\\{i\\}}{\frac{l_{i}^{\alpha}l_{j}^{\alpha}}{d_{ij}^{\alpha}d_{ji}^{\alpha}}}=\beta^{2}\sum_{j\in
S\setminus\\{i\\}}{\frac{1}{(2f(1)+1)^{2}}}=\frac{\beta^{2}(|S|-1)}{(2f(1)+1)^{2}},$

which implies that $|S|<\left(\frac{2f(1)+1}{\beta}\right)^{2}+1=O(1)$. Since
$S$ was an arbitrary feasible subset of $L$, we conclude that $L$ cannot be
split into less than $\Theta(n)$ feasible subsets. ∎

Acknowledgements. We thank Christian Konrad and Jaikumar Radhakrishnan for
helpful suggestions.

## References

  * [1] K. Akcoglu, J. Aspnes, B. DasGupta, and M.-Y. Kao.  Opportunity-cost algorithms for combinatorial auctions.  In E. J. Kontoghiorghes, B. Rustem, and S. Siokos, editors, Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance, pages 455–479. Kluwer Academic Publishers, 2002.
  * [2] L. Barriére, P. Fraigniaud, L. Narayanan, and J. Opatrny.  Robust position-based routing in wireless ad hoc networks with irregular transmission ranges.  Wireless Communications and Mobile Computing, 3(2):141–153, 2003\.
  * [3] M. Bodlaender and M. M. Halldórsson.  Beyond geometry: Towards fully realistic wireless models.  In PODC, 2014.
  * [4] D. Chafekar, V. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan.  Cross-layer latency minimization for wireless networks using SINR constraints.  In Mobihoc, 2007.
  * [5] R. L. Cruz and A. Santhanam.  Optimal Routing, Link Scheduling, and Power Control in Multi-hop Wireless Networks.  In INFOCOM, 2003.
  * [6] J. Dams, M. Hoefer, and T. Kesselheim.  Scheduling in wireless networks with Rayleigh-fading interference.  In SPAA, pages 327–335, 2012.
  * [7] T. ElBatt and A. Ephremides.  Joint Scheduling and Power Control for Wireless Ad-hoc Networks.  In INFOCOM, 2002.
  * [8] A. Fanghänel, T. Kesselheim, H. Räcke, and B. Vöcking.  Oblivious interference scheduling.  In PODC, pages 220–229, 2009.
  * [9] A. Fanghänel, T. Kesselheim, and B. Vöcking.  Improved algorithms for latency minimization in wireless networks.  Theoretical Computer Science, 412(24):2657–2667, 2011.
  * [10] A. Fanghänel and B. Vöcking.  Scheduling and power assignments in the physical model.  In S. Nikoletseas and J. D. Rolim, editors, Theoretical Aspects of Distributed Computing in Sensor Networks, Monographs in Theoretical Computer Science. An EATCS Series, pages 31–57. Springer, 2011.
  * [11] L. Fu, S. C. Liew, and J. Huang.  Power controlled scheduling with consecutive transmission constraints: complexity analysis and algorithm design.  In INFOCOM, pages 1530–1538. IEEE, 2009.
  * [12] O. Goussevskaia, M. M. Halldórsson, and R. Wattenhofer.  Algorithms for wireless capacity.  IEEE/ACM Trans. Netw., 22(3):745–755, 2014.
  * [13] O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer.  Complexity in geometric SINR.  In MobiHoc, pages 100–109, 2007.
  * [14] H. Gudmundsdottir, E. I. Ásgeirsson, M. Bodlaender, J. T. Foley, M. M. Halldórsson, and Y. Vigfusson.  Measurement based interference models for wireless scheduling algorithms.  In MSWiM, 2014.  arXiv:1401.1723.
  * [15] P. Gupta and P. R. Kumar.  The Capacity of Wireless Networks.  IEEE Trans. Information Theory, 46(2):388–404, 2000.
  * [16] M. Halldórsson and C. Newport.  Making wireless algorithm theory more useful: Five ideas from the 2013 Workshop on Realistic Models for Algorithms in Wireless Networks.  ACM SIGACT News, 45(3):72–74, 2014.
  * [17] M. M. Halldórsson.  Wireless scheduling with power control.  ACM Transactions on Algorithms, 9(1):7, December 2012.
  * [18] M. M. Halldórsson and J. Bang-Jensen.  A note on vertex coloring edge-weighted digraphs.  Technical Report 29, Institute Mittag-Leffler, Preprints Graphs, Hypergraphs, and Computing, 2014.
  * [19] M. M. Halldórsson and P. Mitra.  Wireless capacity and admission control in cognitive radio.  In INFOCOM, pages 855–863, 2012.
  * [20] M. M. Halldórsson and P. Mitra.  Wireless Connectivity and Capacity.  In SODA, 2012.
  * [21] M. M. Halldórsson and R. Wattenhofer.  Wireless communication is in APX.  In ICALP, pages 525–536, 2009.
  * [22] J. Heinonen.  Lectures on Analysis on Metric Spaces.  Springer, 1 edition, 2000.
  * [23] M. Hoefer and T. Kesselheim.  Secondary spectrum auctions for symmetric and submodular bidders.  In EC, pages 657–671, 2012.
  * [24] M. Hoefer, T. Kesselheim, and B. Vöcking.  Approximation algorithms for secondary spectrum auctions.  In SPAA, pages 177–186, 2011.
  * [25] K. Jansen, C. Mathieu, H. Shachnai, and N. E. Young.  Packing and scheduling algorithms for information and communication services.  Report from Dagstuhl Seminar 11091, March 2011.
  * [26] F. Kammer and T. Tholey.  Approximation algorithms for intersection graphs.  Algorithmica, 68(2):312–336, 2014.
  * [27] B. Katz, M. Volker, and D. Wagner.  Energy efficient scheduling with power control for wireless networks.  In WiOpt, pages 160–169. IEEE, 2010.
  * [28] T. Kesselheim.  A constant-factor approximation for wireless capacity maximization with power control in the SINR model.  In SODA, pages 1549–1559, 2011.
  * [29] T. Kesselheim.  Approximation algorithms for wireless link scheduling with flexible data rates.  In ESA, pages 659–670, 2012.
  * [30] T. Kesselheim.  Dynamic packet scheduling in wireless networks.  In PODC, pages 281–290, 2012.
  * [31] T. Kesselheim and B. Vöcking.  Distributed contention resolution in wireless networks.  In DISC, pages 163–178. Springer, 2010.
  * [32] F. Kuhn, N. Lynch, C. Newport, R. Oshman, and A. Richa.  Broadcasting in unreliable radio networks.  In PODC, pages 336–345. ACM, 2010.
  * [33] F. Kuhn, R. Wattenhofer, and A. Zollinger.  Ad-hoc networks beyond unit disk graphs.  In FOMC, pages 69–78. ACM, 2003.
  * [34] H. Lin and F. Schalekamp.  On the complexity of the minimum latency scheduling problem on the Euclidean plane.  arXiv preprint 1203.2725, 2012.
  * [35] T. Locher, P. von Rickenbach, and R. Wattenhofer.  Sensor networks continue to puzzle: Selected open problems.  In ICDCN, pages 25–38. Springer, 2008.
  * [36] R. Maheshwari, S. Jain, and S. R. Das.  A measurement study of interference modeling and scheduling in low-power wireless networks.  In SenSys, pages 141–154, 2008.
  * [37] T. Moscibroda and R. Wattenhofer.  The complexity of connectivity in wireless networks.  In INFOCOM, pages 1–13, 2006.
  * [38] T. Moscibroda, R. Wattenhofer, and Y. Weber.  Protocol design beyond graph-based models.  In HotNets, 2006.
  * [39] C. H. Papadimitriou.  Np-completeness: A retrospective.  In ICALP, pages 2–6. Springer, 1997.
  * [40] T. S. Rappaport.  Wireless Communications: Principles and Practice.  Prentice Hall, 2 edition, 2002.
  * [41] J. Ryu, C. Joo, T. T. Kwon, N. B. Shroff, and Y. Choi.  DSS: Distributed SINR-based scheduling algorithm for multihop wireless networks.  IEEE Trans. Mobile Computing, 12(6):1120–1132, 2013.
  * [42] V. Sevani and B. Raman.  SIR based interference modeling for wireless mesh networks: A detailed measurement study.  In COMSNETS. IEEE, 2012.
  * [43] D. Son, B. Krishnamachari, and J. Heidemann.  Experimental study of concurrent transmission in wireless sensor networks.  In SenSys, pages 237–250. ACM, 2006.
  * [44] L. Tassiulas and A. Ephremides.  Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks.  IEEE Trans. Automat. Contr., 37(12):1936–1948, 1992.
  * [45] T. Tonoyan.  On some bounds on the optimum schedule length in the SINR model.  In ALGOSENSORS, pages 120–131, 2012.
  * [46] T. Tonoyan.  Conflict graphs and the capacity of the mean power scheme.  In ALGOSENSORS, 2013.
  * [47] P. Wan, O. Frieder, X. Jia, F. F. Yao, X. Xu, and S. Tang.  Wireless link scheduling under physical interference model.  In INFOCOM, pages 838–845, 2011.
  * [48] E. Welzl.  Blue-dominant centers.  Unpublished memorandum, June 2008.
  * [49] Y. Ye and A. Borodin.  Elimination graphs.  ACM Transactions on Algorithms, 8(2):14:1–14:23, 2012.