.png){kind=icon}
.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper investigates the Min-Max Partial Tree Cover (MinMaxPTC) problem. Given an edge-weighted graph G=(V,E), an integer k and a real number q is an element of R+, each vertex is associated with a non-negative profit, the MinMaxPTC problem asks for k trees to collect profit at least q (that is, the total profit of those vertices covered by these trees is no less than q) such that the weight of a heaviest tree is minimized. In its rooted version, the Rooted Min-Max Partial Tree Cover (R-MinMaxPTC) problem, every tree is required to contain a prescribed vertex (called root). For MinMaxPTC, we propose a (1-e-alpha,1+epsilon), 1+\varepsilon )$$\end{document}-bicriteria approximation algorithm, which computes k trees collecting profit at least alpha q such that the weight of a heaviest tree computed by the algorithm does not exceed 1+epsilon times the optimal weight, where alpha is the approximation ratio for the Budgeted Tree Cover (BTC) problem. The algorithm can be generalized to deal with the R-MinMaxPTC problem, yielding an (alpha ' 1+alpha ',1+epsilon)-bicriteria approximation, where alpha is the approximation ratio for the rooted BTC problem. We also present an (1+epsilon)& centerdot;log1+alpha ' q+1-approximation algorithm for R-MinMaxPTC without violating feasibility.
Keywords:
Min-max tree cover
Partial cover
Budgeted forest cover
Approximation algorithm
Bicriteria algorithm
Journal
M
IF:
1.2
Papers:
24
Citations:
0