论文标题
通过LP圆形覆盖大约在下限和上限
Approximate Covering with Lower and Upper Bounds via LP Rounding
论文作者
论文摘要
在本文中，我们研究了下层和上限的覆盖物（LUC）问题，在其中我们获得了$ n $ point的$ p $ p $ p $，收集$ \ mathcal {b} $的球以及参数$ l $和$ u $。目的是找到一个最小尺寸的子集$ \ Mathcal {b}'\ subseteq \ Mathcal {b} $，并在$ p $到$ \ nathcal {b} $中分配点的分配，以便每个点$ p \ in P $中的每个点$ p \ in Co $ p $ b $ b_i} in ATA $ L $，最多$ u $点分配给$ b_i $。我们通过小恒定因子违反了下限和上限的约束，从而获得了基于LP圆形的常数近似，并再次通过小恒定因子扩展球。以前知道仅涵盖上限约束的问题以前已经知道了类似的结果。我们还表明，只有下限约束，可以在没有任何下限违规的情况下获得上述结果。 涵盖问题与设施位置问题有密切的联系。我们注意到，对于相应的下层和上限设施位置问题，已知的常数 - 附近临时，违反了恒定因子的上限和上限约束。
In this paper, we study the lower- and upper-bounded covering (LUC) problem, where we are given a set $P$ of $n$ points, a collection $\mathcal{B}$ of balls, and parameters $L$ and $U$. The goal is to find a minimum-sized subset $\mathcal{B}'\subseteq \mathcal{B}$ and an assignment of the points in $P$ to $\mathcal{B}'$, such that each point $p\in P$ is assigned to a ball that contains $p$ and for each ball $B_i\in \mathcal{B}'$, at least $L$ and at most $U$ points are assigned to $B_i$. We obtain an LP rounding based constant approximation for LUC by violating the lower and upper bound constraints by small constant factors and expanding the balls by again a small constant factor. Similar results were known before for covering problems with only the upper bound constraint. We also show that with only the lower bound constraint, the above result can be obtained without any lower bound violation. Covering problems have close connections with facility location problems. We note that the known constant-approximation for the corresponding lower- and upper-bounded facility location problem, violates the lower and upper bound constraints by a constant factor.
