Maximizing submodular set function with connectivity constraint: Theory and application to networks

Tung Wei Kuo, Ching-Ju Lin, Ming Jer Tsai

研究成果: Conference contribution同行評審

12 引文 斯高帕斯(Scopus)

摘要

In this paper, we investigate the wireless network deployment problem, which seeks the best deployment of a given limited number of wireless routers. We found that many goals for network deployment, such as maximizing the number of covered users or areas, or the total throughput of the network, can be modelled with the submodular set function. Specifically, given a set of routers, the goal is to find a set of locations S, each of which is equipped with a router, such that S maximizes a predefined submodular set function. However, this deployment problem is more difficult than the traditional maximum submodular set function problem, e.g., the maximum coverage problem, because it requires all the deployed routers to form a connected network. In addition, deploying a router in different locations might consume different costs. To address these challenges, this paper introduces two approximation algorithms, one for homogeneous deployment cost scenarios and the other for heterogeneous deployment cost scenarios. Our simulations, using synthetic data and real traces of census in Taipei, show that the proposed algorithms achieve a better performance than other heuristics.

原文English
主出版物標題2013 Proceedings IEEE INFOCOM 2013
頁面1977-1985
頁數9
DOIs
出版狀態Published - 2013
事件32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
持續時間: 14 4月 201319 4月 2013

出版系列

名字Proceedings - IEEE INFOCOM
ISSN(列印)0743-166X

Conference

Conference32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013
國家/地區Italy
城市Turin
期間14/04/1319/04/13

指紋

深入研究「Maximizing submodular set function with connectivity constraint: Theory and application to networks」主題。共同形成了獨特的指紋。

引用此