The minimum clearing time problem in wireless networks

The thesis focuses on the minimum time clearing objective for link scheduling in wireless networks. We formulate the problem as a deterministic LP. We relate the problem to other works on capacity and scheduling. In general, the problem is NP-complete. We consider special networks where the additional structure makes the problem tractable. We argue that explicitly solving the linear program is implausible. And proceed to show that the problemis amenable to a greedy allocation scheme that only requires local information. Beyond the special case, we consider simple ring networks where in general, the greedy solution is sub-optimal. We solve the minimum clearing time problem for ring networks under 1-hop interference model. We establish the sufficiency conditions for optimality of a greedy solution. We also provide the solution when these conditions do not hold. For this case, the solution depends on global information, unlike the greedy solution. However, the solution only has a linear complexity in terms of computation. The minimum clearing time problem can help us understand how the network is constrained under different load distributions. Ultimately, in the future we aim to use these insights to design a simple scheduling policy, with nearly optimal performance in a general wireless network.