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.