|
This paper considers the NP-hard problem of scheduling weighted links in concurrent transmit/receive wireless mesh networks. The problem generalizes existing works to links with weight $w_{ij}\ge 1$. We propose an O($|V|^2$) algorithm, where $V$ is the set of routers, that is ordersof magnitude faster than computationally intensive approaches that use the well-known Goemans-Williamson (GWA)'s maximum cut algorithm and also brute-force. Our algorithm generates schedules, on average, with at most 3\% and 9\% fewer links that the GWA and brute-force approaches respectievly.
|