Approximation algorithm for unrooted prize-collecting forest with multiple components and its application on prize-collecting sweep coverage

• 成果类型: Article; Early Access
• 署名作者: Liang, Wei; Tang, Shaojie; Zhang, Zhao
• 署名单位: Zhejiang Normal University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02275-4
• 发表日期: 2025
• 关键词: steiner tree

摘要

In this paper, we introduce a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with K Components (URPCFK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {URPCF}_K$$\end{document}) problem. Given a graph G and an integer K, URPCFK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {URPCF}_K$$\end{document} aims to find a forest with exactly K connected components while minimizing the sum of the forest's cost and the penalties incurred by unspanned vertices. Unlike the rooted version RPCFK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {RPCF}_K$$\end{document}, where a 2-approximation algorithm exists, solving the unrooted version by guessing roots leads to exponential time complexity for non-constant K. To address this challenge, we propose a rootless growing and rootless pruning algorithm. We also apply this algorithm to improve the approximation ratio for the Prize-Collecting Min-Sensor Sweep Cover problem (PCMinSSC) from 8 to 5.