Improved Bounds for Online Dominating Sets of Trees
Improved Bounds for Online Dominating Sets of Trees
复制标题
DOI：
10.4230/lipics.isaac.2017.52
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Koji M. Kobayashi
中科院分区：
文献类型：
--
作者：
Koji M. Kobayashi
在线控制集问题是图的最小控制集问题的在线变体，最小控制集问题是图上最重要的NP-难问题之一。这个问题的定义如下：给定一个无向图$G =（V，E）$，其中$V$是一个顶点集，$E$是一个边集。我们说一个顶点集$D \subseteq V$是$G$的一个{\em支配集}，如果对于V \setminus D$中的每个$v \，在D$中存在一个顶点$u \，使得$\{ u，v \} \in E$。随着时间的推移，顶点被一个接一个地显示给在线算法。当一个顶点被揭示时，顶点和过去揭示的顶点之间的边也被揭示。一个revelaed子树是连接在任何时候。一个在线算法可以在每个顶点显示后立即选择已经显示的顶点，并且必须保持到目前为止显示的图的支配集。算法在给定树上的代价是它所选择的顶点数，其目标是使代价最小化。Escherbenz（Technical report，Institute of Theoretical Computer Science，ETH Zu rich，2002）and Boyar et al. (SWAT 2016）研究了给定图是树的情况。他们设计了一个确定性在线算法，其竞争比最多为3，并证明了任何确定性算法的竞争比的下限为2。在本文中，我们也关注树木。我们建立了一个匹配的下限任何确定性算法。此外，我们设计了一个随机在线算法，其竞争比最多为5/2 = 2.5$，并证明了任何随机算法的竞争比至少为4/3 \approximat1.333 $。
The online dominating set problem is an online variant of the minimum dominating set problem, which is one of the most important NP-hard problems on graphs. This problem is defined as follows: Given an undirected graph $G = (V, E)$, in which $V$ is a set of vertices and $E$ is a set of edges. We say that a set $D \subseteq V$ of vertices is a {\em dominating set} of $G$ if for each $v \in V \setminus D$, there exists a vertex $u \in D$ such that $\{ u, v \} \in E$. The vertices are revealed to an online algorithm one by one over time. When a vertex is revealed, edges between the vertex and vertices revealed in the past are also revealed. A revelaed subtree is connected at any time. Immediately after the revelation of each vertex, an online algorithm can choose vertices which were already revealed irrevocably and must maintain a dominating set of a graph revealed so far. The cost of an algorithm on a given tree is the number of vertices chosen by it, and its objective is to minimize the cost. Eidenbenz (Technical report, Institute of Theoretical Computer Science, ETH Z\"{u}rich, 2002) and Boyar et al.\ (SWAT 2016) studied the case in which given graphs are trees. They designed a deterministic online algorithm whose competitive ratio is at most three, and proved that a lower bound on the competitive ratio of any deterministic algorithm is two. In this paper, we also focus on trees. We establish a matching lower bound for any deterministic algorithm. Moreover, we design a randomized online algorithm whose competitive ratio is at most $5/2 = 2.5$, and show that the competitive ratio of any randomized algorithm is at least $4/3 \approx 1.333$.