论文标题
多控制问题的近似算法
Approximation algorithm for the Multicovering Problem
论文作者
论文摘要
令$ \ MATHCAL {H} =（V，\ Mathcal {E}）$为具有最大边缘尺寸$ \ ell $和最大度$δ$的超图。 For given numbers $b_v\in \mathbb{N}_{\geq 2}$, $v\in V$, a set multicover in $\mathcal{H}$ is a set of edges $C \subseteq \mathcal{E}$ such that every vertex $v$ in $V$ belongs to at least $b_v$ edges in $C$.设置多倍是找到最小信用额度多倍的问题。 Peleg，Schechtman和Wool猜想，对于任何固定的$δ$和$ b：= \ min_ {v \ in V} b_ {V} $，\ sbmultCov的问题在比率少于$δ：=δ-b+1 $的比率下不可能。因此，要探索该猜想不存在的超图类别是一个挑战。 我们为设定的多次问题提供了多项式时间算法，该算法将确定性阈值算法与条件随机舍入步骤结合在一起。我们的算法产生的近似值为$ \ max \ weft \ {\ frac {148} {149} {Δ，\ left（1- \ frac {（b-1）我们的结果不仅比Srivastav等人提出的近似值（Algorithmica 2016）提高了，而且由于我们对参数$ \ ell $的限制没有限制，因此更为笼统。此外，我们提出了另一种多项式时间算法，其近似值为$ \ frac {5} {6} {6}Δ$，用于$ \ ell \ ell \ leq（1+ε）\ bar {\ ell} $的超图，对于任何固定的$ε\ in [0，\ frac {$ frac} $ {$ ell {$ im} $ {2}边缘大小。对该算法的分析依赖于与Ray-Chaudhuri（1960）引起的匹配/覆盖二元性，我们将其转化为近似形式。第二个表现反驳了Peleg等人的猜想，以示超图的大型亚类。
Let $\mathcal{H}=(V,\mathcal{E})$ be a hypergraph with maximum edge size $\ell$ and maximum degree $Δ$. For given numbers $b_v\in \mathbb{N}_{\geq 2}$, $v\in V$, a set multicover in $\mathcal{H}$ is a set of edges $C \subseteq \mathcal{E}$ such that every vertex $v$ in $V$ belongs to at least $b_v$ edges in $C$. Set Multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed $Δ$ and $b:=\min_{v\in V}b_{v}$, the problem of \sbmultcov is not approximable within a ratio less than $δ:=Δ-b+1$, unless $\mathcal{P} =\mathcal{NP}$. Hence it's a challenge to explore for which classes of hypergraph the conjecture doesn't hold. We present a polynomial time algorithm for the Set Multicover problem which combines a deterministic threshold algorithm with conditioned randomized rounding steps. Our algorithm yields an approximation ratio of $ \max\left\{ \frac{148}{149}δ, \left(1- \frac{ (b-1)e^{\fracδ{4}}}{94\ell} \right)δ\right\}$. Our result not only improves over the approximation ratio presented by Srivastav et al (Algorithmica 2016) but it's more general since we set no restriction on the parameter $\ell$. Moreover we present a further polynomial time algorithm with an approximation ratio of $\frac{5}{6}δ$ for hypergraphs with $\ell\leq (1+ε)\bar{\ell}$ for any fixed $ε\in [0,\frac{1}{2}]$, where $\bar{\ell}$ is the average edge size. The analysis of this algorithm relies on matching/covering duality due to Ray-Chaudhuri (1960), which we convert into an approximative form. The second performance disprove the conjecture of peleg et al for a large subclass of hypergraphs.
