This paper investigates the Min-Max Partial Tree Cover (MinMaxPTC) problem. Given an edge-weighted graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$G=(V,E)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, an integer k and a real number <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$q \in \mathbb {R}^+ $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mo>+</mo> </msup> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(1-e^{-\alpha }, 1+\varepsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <msup> <mi>e</mi> <mrow> <mo>-</mo> <mi>α</mi> </mrow> </msup> <mo>,</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-bicriteria approximation algorithm, which computes k trees collecting profit at least <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\alpha q$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mi>q</mi> </mrow> </math></EquationSource> </InlineEquation> such that the weight of a heaviest tree computed by the algorithm does not exceed <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$1+\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>+</mo> <mi>ε</mi> </mrow> </math></EquationSource> </InlineEquation> times the optimal weight, where <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$(\frac{\alpha '}{1+\alpha '},1+\varepsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mfrac> <msup> <mi>α</mi> <mo>′</mo> </msup> <mrow> <mn>1</mn> <mo>+</mo> <msup> <mi>α</mi> <mo>′</mo> </msup> </mrow> </mfrac> <mo>,</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-bicriteria approximation, where <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\alpha '$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>α</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> is the approximation ratio for the rooted BTC problem. We also present an <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$(1+\varepsilon )\cdot \left( \lceil \log _{1+\alpha '}q\rceil +1\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> <mo>·</mo> <mfenced close=")" open="("> <mo>⌈</mo> <msub> <mo>log</mo> <mrow> <mn>1</mn> <mo>+</mo> <msup> <mi>α</mi> <mo>′</mo> </msup> </mrow> </msub> <mi>q</mi> <mo>⌉</mo> <mo>+</mo> <mn>1</mn> </mfenced> </mrow> </math></EquationSource> </InlineEquation>-approximation algorithm for R-MinMaxPTC without violating feasibility.

Approximation algorithm for the Min-Max partial tree cover problem

期刊论文
发表日期：

2026年4月3日

查看全文

Lei Zhao,
Zhao Zhang

摘要

This paper investigates the Min-Max Partial Tree Cover (MinMaxPTC) problem. Given an edge-weighted graph $G=(V,E)$ $G = (V, E)$ , an integer k and a real number $q \in \mathbb {R}^+ $ $q \in 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+\varepsilon )$ $(1 - e^{- α}, 1 + ε)$ -bicriteria approximation algorithm, which computes k trees collecting profit at least $\alpha q$ $α q$ such that the weight of a heaviest tree computed by the algorithm does not exceed $1+\varepsilon $ $1 + ε$ 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 $(\frac{\alpha '}{1+\alpha '},1+\varepsilon )$ $(\frac{α^{'}}{1 + α^{'}}, 1 + ε)$ -bicriteria approximation, where $\alpha '$ $α^{'}$ is the approximation ratio for the rooted BTC problem. We also present an $(1+\varepsilon )\cdot \left( \lceil \log _{1+\alpha '}q\rceil +1\right) $ $(1 + ε) \cdot (⌈ {log}_{1 + α^{'}} q ⌉ + 1)$ -approximation algorithm for R-MinMaxPTC without violating feasibility.