论文标题
在几何设置中区分和识别代码问题的复杂性和近似值
Complexity and Approximation for Discriminating and Identifying Code Problems in Geometric Setups
论文作者
论文摘要
我们研究区分代码问题的几何变化。在问题的\ emph {iNdeTe版本}中，一组有限的点$ p $和有限的对象$ s $在$ \ mathbb {r}^d $中给出。目的是选择最低基数的子集$ s^* \子群s $，以便在p $中的每个点$ p_i \，子集$ s_i^* \ subseteq s^* $覆盖$ p_i $ covering $ p_i $满足$ s_i^* \ neq neq \ neq \ emptyset $，ne $ p_i $ p_i，p_ $，p_ $，我们的p_j $ $ s_i^* \ neq s_j^* $。在问题的\ emph {连续版本}中，解决方案集$ s^*$可以自由选择（潜在的无限）类允许的几何对象。在一维情况（$ d = 1 $）中，$ P $中的点位于水平线$ L $上，$ S $中的对象是与$ L $对齐的有限长度线段（称为间隔）。我们表明，此问题的离散版本是NP完整的。这有点令人惊讶，因为已知连续版本可以解决多项式时间。尽管如此，对于一维离散版本，我们设计了一个多项式时间$ 2 $ - APPROXIMATION算法。我们还在一个维度上为离散版本和连续版本设计一个PTA，对于间隔都具有相同长度所需的限制。然后，我们研究轴 - 平行单位方形对象的二维情况（$ d = 2 $）。我们表明，连续版本和离散版本都是NP完整的，并且设计了产生$ $的多项式近似算法（16 \ cdot opt+1）$ - 近似值和$（64 \ cdot opt+1）$ - 近似解决方案，使用适当定义的Integer Integer线性线性编程问题的舍入。我们表明，可以以与单位平方对象的离散版本的区分代码问题相同的方式求解轴平行单元平方体交点图（以$ d = 2 $）的识别代码问题。
We study geometric variations of the discriminating code problem. In the \emph{discrete version} of the problem, a finite set of points $P$ and a finite set of objects $S$ are given in $\mathbb{R}^d$. The objective is to choose a subset $S^* \subseteq S$ of minimum cardinality such that for each point $p_i \in P$, the subset $S_i^* \subseteq S^*$ covering $p_i$ satisfies $S_i^*\neq \emptyset$, and each pair $p_i,p_j \in P$, $i \neq j$, we have $S_i^* \neq S_j^*$. In the \emph{continuous version} of the problem, the solution set $S^*$ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ($d=1$), the points in $P$ are placed on a horizontal line $L$, and the objects in $S$ are finite-length line segments aligned with $L$ (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. Still, for the 1-dimensional discrete version, we design a polynomial-time $2$-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ($d=2$) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce $(16\cdot OPT+1)$-approximate and $(64\cdot OPT+1)$-approximate solutions respectively, using rounding of suitably defined integer linear programming problems. We show that the identifying code problem for axis-parallel unit square intersection graphs (in $d=2$) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects.
