An approximation algorithm for maximum weight budgeted connected set cover

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2016-05

期刊名稱

JOURNAL OF COMBINATORIAL OPTIMIZATION

卷期與頁次

第 31 卷第 4 期,頁 1505–1517

ISSN

1382-6905

語言

英文

摘要

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 .

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

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

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/133401