Complexity in geometric SINR
Authors:
Open Access
- 9 September 2007
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 100-109
Abstract
In this paper we study the problem of scheduling wireless links in the geometric SINR model, which explicitly uses the fact that nodes are distributed in the Euclidean plane. We present the first NP-completeness proofs in such a model. In particular, we prove two problems to be NP-complete: Scheduling and One-Shot Scheduling. The first problem consists in finding a minimum-length schedule for a given set of links. The second problem receives a weighted set of links as input and consists in finding a maximum-weight subset of links to be scheduled simultaneously in one shot. In addition to the complexity proofs, we devise an approximation algorithm for each problem.Keywords
This publication has 26 references indexed in Scilit:
- A column generation method for spatial TDMA scheduling in ad hoc networksAd Hoc Networks, 2004
- Optimal Power Control, Scheduling, and Routing in UWB NetworksIEEE Journal on Selected Areas in Communications, 2004
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000
- PAMAS—power aware multi-access protocol with signalling for ad hoc networksACM SIGCOMM Computer Communication Review, 1998
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric GraphsJournal of Algorithms, 1998
- Joint optimal channel base station and power assignment for wireless accessIEEE/ACM Transactions on Networking, 1996
- Scheduling algorithms for multihop radio networksIEEE/ACM Transactions on Networking, 1993
- Scheduling broadcasts in multihop radio networksIEEE Transactions on Communications, 1990
- Link scheduling in polynomial timeIEEE Transactions on Information Theory, 1988
- Reducibility among Combinatorial Problems1972