**A
Note on Precedence in Link Scheduling**

Magnús M. Halldórsson / 8 October 2012

A fundamental problem in wireless algorithmics
is the *link capacity* problem, also known as single-slot scheduling, and
maximum independent set of links. The first constant factor approximation for
the link capacity problem was given in [1]. It introduced a way of turning
interference into an linear additive expression, which was called *affectedness*.
Unfortunately, that definition contained a mistake in the way noise was
factored in, which meant that the constant-factor bound did not hold for the
case when most of the links were very weak. This mistake was discovered by the
authors and corrected in a follow-up paper [2], with a modified definition of *affectance.*

A shortly after, another paper appeared that claimed to give the first constant factor approximation result for the general link capacity problem [3]. The authors of that paper were unaware of the earlier correction [2], and did not try to clarify the issue with the authors of [1]. Even now, when contributions should be clear, there have been numerous recent papers asserting that [3] contained the first constant approximation result for link capacity. The purpose of this note is to clarify the proper attribution of credit.

Even if one would want to give the authors of
[3] credit for a simultaneous discovery, this must involve an assessment of the
true scientific contribution. In particular, it should be noted that the
algorithm of [3] is in fact *identical* to that of [2], modulo updated
expression. No such credit is given in [3], the appropriateness of which is
left to the reader. Also, the analysis follows the same basic pattern (e.g.,
bounding nearby nodes separately, dividing the plane into 60 degree wedges,
etc). In fact, there are no intellectual contributions in [3] that have
influenced later works. The only contribution appears to be to tighten the
constant factors (although the dependence on path-loss constant remains
exponential).

Consequently, it is requested that the work of [1,2] be considered to give the first constant-factor approximation results for link capacity. The work of [3] should be credited with deriving an improved constant.

**References**

[1] Olga Goussevskaia, Magnús M. Halldórsson,
Roger Wattenhofer, and Emo Welzl. Capacity of Arbitrary Wireless Networks. In *INFOCOM
2009*.

[2] Magnús M. Halldórsson, Roger Wattenhofer.
Wireless Communication is in APX. In *ICALP 2009.*

[3] Peng-Jun Wan, Xiaohua Jia, and Frances Yao.
Maximum Independent Set of Links under Physical Interference Model. In *WASA
2009*, LNCS 5682, pp. 169–178, 2009.