This talk is about three important problems in constrained networks: (1) High-performance packet scheduling, (2) Feasible rate-allocation and (3) Computation of loss probability. In general, these problems are computationally hard. We will identify constraint graph structures, which we call ``non-expanding'', that are likely to appear in practice and allow for efficient algorithm design for the three problems. We will explain algorithm for packet scheduling in the context of wireless network with independent set constraint. The algorithm is based on a distributed randomized graph partitioning scheme. Time permitting, we will explain its relation to problems (2) and (3).
This talk is based on joint work with Kyo min Jung, MIT.