.png){kind=icon}
返回
Approximation algorithm for the Min-Max partial tree cover problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s00186-026-00921-x.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文研究了最小最大部分树覆盖（MinMaxPTC）问题。给定一个带权图G=(V,E)，一个整数k和一个正实数q，每个顶点关联一个非负利润，MinMaxPTC问题要求找到k棵树收集至少q的利润（即这些树覆盖的顶点的总利润不小于q），使得最重树的权重最小化。在其根版本中，根最小最大部分树覆盖（R-MinMaxPTC）问题要求每棵树必须包含一个指定顶点（称为根）。对于MinMaxPTC，我们提出一个(1-ε/α,1+ε)-双标准近似算法，该算法计算k棵树收集至少αq的利润，使得算法计算的最重树权重不超过最优权重的1+ε倍，其中α是预算树覆盖（BTC）问题的近似比。该算法可以推广到处理R-MinMaxPTC问题，得到一个(α',1+α',1+ε)-双标准近似，其中α'是根BTC问题的近似比。我们还提出了一个(1+ε)·log(1+α')q+1-近似算法，用于不违反可行性的R-MinMaxPTC问题。
Keyword:
Min-max tree cover
Partial cover
Budgeted forest cover
Approximation algorithm
Bicriteria algorithm
期刊
M
IF:
1.2
论文数:
24
被引数:
0
机构
引用论文
暂无论文信息