An approximation algorithm for maximum weight budgeted connected set cover
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
1517 | en_US |
dc.citation.issue |
4 | en_US |
dc.citation.spage |
1505 | en_US |
dc.citation.volume |
31 | en_US |
dc.contributor.author |
Ran, Yingli | en_US |
dc.contributor.author |
Zhang, Zhao | en_US |
dc.contributor.author |
Ko, Ker-I | en_US |
dc.contributor.author |
Liang, Jun | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2017-04-21T06:55:47Z | |
dc.date.available |
2017-04-21T06:55:47Z | |
dc.date.issued |
2016-05 | en_US |
dc.description.abstract |
This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected graph (called communication graph) on vertex set , and a budget , the MWBCSC problem is to select a subcollection such that the cost , the subgraph of induced by is connected, and the total weight of elements covered by (that is ) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio , where is the maximum degree of graph and is the number of sets in . In particular, if every set has cost at most , the performance ratio can be improved to . | en_US |
dc.identifier.doi |
10.1007/s10878-015-9838-1 | en_US |
dc.identifier.issn |
1382-6905 | en_US |
dc.identifier.journal |
JOURNAL OF COMBINATORIAL OPTIMIZATION | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1007/s10878-015-9838-1 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/133401 | |
dc.identifier.wosnumber |
WOS:000373574300011 | en_US |
dc.language.iso |
en_US | en_US |
dc.subject |
Budgeted set cover | en_US |
dc.subject |
Connected set cover | en_US |
dc.subject |
Approximation algorithm | en_US |
dc.title |
An approximation algorithm for maximum weight budgeted connected set cover | en_US |
檔案
本條目沒有附加檔案。
所屬典藏: 期刊論文
引用此條目
Ran, Y., Zhang, Z., Ko, K.-I., & Liang, J. (2016). An approximation algorithm for maximum weight budgeted connected set cover. JOURNAL OF COMBINATORIAL OPTIMIZATION, 31(4), 1505–1517. https://doi.org/10.1007/s10878-015-9838-1
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/133401