グラフ・ネットワークにおける理論と最適化グループセミナー
日時
2013年4月22日 (月) 11:00 ～ 12:30
場所
国立情報学研究所 2208号室
講演者
Magnus M. Halldorsson 先生（Reykjavik University）
タイトル
Algorithms for throughput and scheduling in wireless networks
アブストラクト
Wireless communication continues to have tremendous social impact. From an algorithmic point of view, a major challenge in wireless computing is to find general models of interference that are both realistic and analytically feasible. The previously studied graph models lack the fading and the additivity properties of real-world wireless communication. We survey recent work on algorithms in the SINR or physical model, focusing on the core MAC-layer problems of link scheduling and throughput maximization. Combinatorially, these can be modeled as packing and partitioning problems in directed edge-weighted graphs obeying certain geometric inequalities. We find that these graphs satisfy a certain “inductiveness” property that allows for good throughput approximations. With appropriate power control, we show that we can actually achieve locality in the SINR model, leading to efficient solution of certain scheduling problems as well. Parts of this research is joint work with Pradipta Mitra, Stephan Holzer and Roger Wattenhofer.
