论文标题
在几何设置下，最低$ p $ UNIM $ P $ UNIM的近似算法
Approximation Algorithm for Minimum $p$ Union Under a Geometric Setting
论文作者
论文摘要
在至少$ p $ Union问题（Min $ P $ U）中，给定超graph $ g =（v，e）$和整数$ p $，目标是找到一组$ p $ hyperedges $ e'\ subseteq e $，以便$ e'$覆盖的顶点的数量是$ e'$（那就是$ | | \ bigcup_ iS e |众所周知，Min $ p $ U至少与最密集的$ k $ -subgraph问题一样困难。一个问题是：在某些几何设置中的问题如何？在本文中，我们考虑了单位平方最小$ p $ u问题（最小$ p $ u-us），其中$ v $是飞机上的一组点，每个$ e $的每个超edge都由单位广场中的一组点组成。 a $（\ frac {1} {1+ \ varepsilon}，4）$ - 双粒子近似算法，也就是说，算法找到至少$ \ frac {p} {p} {p} {1+ \ varepsilon} $ point $ point $ point $ $ $ - $ 4op $ pote $ 4op $ $ 4opt $ $ 4opt $ $ 4opt $ $ 4opt $ $ 4opt $ $ 4opt $ 4opt $ $ 4opt $ $ 4opt $ us us $ 4opt （$ p $单位正方形可以覆盖的最低点数）。
In a minimum $p$ union problem (Min$p$U), given a hypergraph $G=(V,E)$ and an integer $p$, the goal is to find a set of $p$ hyperedges $E'\subseteq E$ such that the number of vertices covered by $E'$ (that is $|\bigcup_{e\in E'}e|$) is minimized. It was known that Min$p$U is at least as hard as the densest $k$-subgraph problem. A question is: how about the problem in some geometric settings? In this paper, we consider the unit square Min$p$U problem (Min$p$U-US) in which $V$ is a set of points on the plane, and each hyperedge of $E$ consists of a set of points in a unit square. A $(\frac{1}{1+\varepsilon},4)$-bicriteria approximation algorithm is presented, that is, the algorithm finds at least $\frac{p}{1+\varepsilon}$ unit squares covering at most $4opt$ points, where $opt$ is the optimal value for the Min$p$U-US instance (the minimum number of points that can be covered by $p$ unit squares).
