We consider the online hitting set problem for the range space $\Sigma=(\cal X,\cal R)$, where the point set $\cal X$ is known beforehand, but the set $\cal R$ of geometric objects is not known in advance. Here, geometric objects arrive one by one, the objective is to maintain a hitting set of minimum cardinality by taking irrevocable decisions. In this paper, we have considered the problem when the objects are unit balls or unit hypercubes in $\mathbb{R}^d$, and the points from $\mathbb{Z}^d$ are used for hitting them. First, we consider the problem for objects (unit balls and unit hypercubes) in lower dimensions. We obtain $4$ and $8$-competitive deterministic online algorithms for hitting unit hypercubes in $\mathbb{R}^2$ and $\mathbb{R}^3$, respectively. On the other hand, we present $4$ and $14$-competitive deterministic online algorithms for hitting unit balls in $\mathbb{R}^2$ and $\mathbb{R}^3$, respectively. Next, we consider the problem for objects (unit balls and unit hypercubes) in the higher dimension. For hitting unit hypercubes in $\mathbb{R}^d$, we present a $O(d^2)$-competitive randomized online algorithm for $d\geq 3$ and prove the competitive ratio of any deterministic algorithm for the problem is at least $d+1$ for any $d\in\mathbb{N}$. Then, for hitting unit balls in $\mathbb{R}^d$, we propose a $O(d^4)$-competitive deterministic algorithm, and for $d<4$, we establish that the competitive ratio of any deterministic algorithm is at least $d+1$.


翻译:在$\mathbb{Z}^d$中使用点数击中$\mathbb{R}^d$中单位球和超立方体的在线问题。 我们考虑一个范围空间$\Sigma=(\cal X,\cal R)$的在线击中集问题,其中点集$\cal X$预先知道,但几何对象的集合$\cal R$事先不知道。在这里,几何对象一个接一个地到达,目标是通过做出不可撤销的决策来维护最小的击中集。在本文中,我们考虑了物体为单位球或单位 d 维超立方体的问题,使用来自$\mathbb{Z}^d$的点数进行击中。首先,我们考虑低维物体(单位球和单位超立方体)的问题。 对于在$\mathbb{R}^2$和$\mathbb{R}^3$中的单位超立方体击中,我们得到了$4$和$8$的竞争力的确定性在线算法;对于在$\mathbb{R}^2$和$\mathbb{R}^3$中的单位球击中,我们提出了$4$和$14$的竞争力的确定性在线算法。 接下来,我们考虑更高维度的问题。针对在$\mathbb{R}^d$中的单位超立方体敲定,我们提出了一个$O(d^2)$的随机在线算法,对于任何$d\in\mathbb{N}$,证明了该问题的任何确定性算法的竞争比至少为$d+1$。然后,对于在$\mathbb{R}^d$中敲定单位球,我们提出了一个$O(d^4)$的确定性算法,对于$d<4$,我们确定任何确定性算法的竞争比至少为$d+1$。

0
下载
关闭预览

相关内容

简称 哈工大,创建于1920年,是C9联盟成员之一,国内工科顶尖高校。1999年成为首批九所985工程院校之一,校训是“规格严格,功夫到家”。
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
72+阅读 · 2022年6月28日
【2022新书】谱图理论,Spectral Graph Theory,100页pdf
专知会员服务
74+阅读 · 2022年4月15日
专知会员服务
42+阅读 · 2020年12月18日
【ICLR 2019】双曲注意力网络,Hyperbolic  Attention Network
专知会员服务
82+阅读 · 2020年6月21日
专知会员服务
61+阅读 · 2020年3月4日
专知会员服务
159+阅读 · 2020年1月16日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月9日
Arxiv
0+阅读 · 2023年5月9日
Arxiv
0+阅读 · 2023年5月9日
Arxiv
0+阅读 · 2023年5月8日
Arxiv
12+阅读 · 2022年4月30日
VIP会员
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
2+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员