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 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 Zurich, 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.

The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. We focus on multi-queue switches in QoS networks proposed by Azar et al. They introduced so-called "the relaxed model". Also, they showed that if the competitive ratio of the single-queue model is at most c, and if the competitive ratio of the relaxed model is at most c2, then the competitive ratio of the multi-queue switch model is cc2. They proved that c2d2, and obtained upper bounds on the competitive ratios for several multi-queue switch models.

The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered. In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is 4M-43M-2 in the case of N=2, where N is the number of output ports in a switch and M is the size of the buffer. This matches the lower bound given by Hahne, Kesselman and Mansour. Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2-1M minK=1, 2, ..., N{⌊MK⌋ + K - 1.