论文标题
部分可观测时空混沌系统的无模型预测
Packing, Hitting, and Colouring Squares
论文作者
论文摘要
鉴于飞机上有限的正方形家族，包装问题要求其中的最大数量$ν$ $ν$，而最小数字$τ$点的打击问题击中了所有点。显然，$τ\geν$。已知这两个问题都是NP固定的，即使对于轴平行单位正方形的家族也是如此。 这项工作的主要结果为$τ/ν$比率提供了第一个非平凡界限，而不一定是轴 - 并行正方形。我们建立了单位广场$ 6 $的上限和$ 10 $ $ 10的尺寸。我们可以提供的最差比率分别为$ 3 $和$ 4 $。为了进行比较，在轴平行的情况下，所考虑的比率为间隔$ [\ frac {\ frac {3} {2}，2]，单位正方形和$ [\ frac {\ frac {3} {2} {2}，4] $的正方形尺寸的正方形。我们针对$τ/ν$比率引入的方法也可以用来将色度$χ$和集团数字$ω$的平方$χ/ω$比率与单位广场的$ 6 $ $ 6和$ 9 $相关联。 $τ/ν$和$χ/ω$比率之前已经通过“脂肪”对象的常数来界定，其中最胖，最简单的是磁盘和正方形。但是，尽管磁盘受到了很大的关注，但正方形的特定界限基本上仍未开发。这项工作打算填补这一空白。
Given a finite family of squares in the plane, the packing problem asks for the maximum number $ν$ of pairwise disjoint squares among them, while the hitting problem for the minimum number $τ$ of points hitting all of them. Clearly, $τ\ge ν$. Both problems are known to be NP-hard, even for families of axis-parallel unit squares. The main results of this work provide the first non-trivial bounds for the $τ/ ν$ ratio for not necessarily axis-parallel squares. We establish an upper bound of $6$ for unit squares and $10$ for squares of varying sizes. The worst ratios we can provide with examples are $3$ and $4$, respectively. For comparison, in the axis-parallel case, the supremum of the considered ratio is in the interval $[\frac{3}{2},2]$ for unit squares and $[\frac{3}{2},4]$ for squares of varying sizes. The methods we introduced for the $τ/ν$ ratio can also be used to relate the chromatic number $χ$ and clique number $ω$ of squares by bounding the $χ/ω$ ratio by $6$ for unit squares and $9$ for squares of varying sizes. The $τ/ ν$ and $χ/ω$ ratios have already been bounded before by a constant for "fat" objects, the fattest and simplest of which are disks and squares. However, while disks have received significant attention, specific bounds for squares have remained essentially unexplored. This work intends to fill this gap.
