Algorithms for Spectrum Allocation in Wireless Networks.
Time: 15:30 -- Location: LIX
Scarcity of the frequency spectrum is a major problem in wireless networks, but it is often due to the static allocation rules implemented by regulators. From an algorithmic perspective, flexible allocation of spectrum gives rise to a variety of interesting new optimization problems, most prominently variants of independent set and coloring problems in special graph classes. The talk will survey some of our recent work in this area on design and analysis of algorithms with connections to game theory. Our goal is to design efficient approximation algorithms the come with provable results for running time, solution quality, and incentives.