Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer Science and Business Media LLC  

Abstract

The online graph exploration problem, which was proposed by Kalyanasundaram and Pruhs (Theor Comput Sci 130(1):125–138, 1994), is defined as follows: Given an edge-weighted undirected connected graph and a specified vertex (called the origin), the task of an algorithm is to compute a path from the origin to the origin which contains all the vertices of the given graph. The goal of the problem is to find such a path of minimum weight. At each time, an online algorithm knows only the weights of edges each of which consists of visited vertices or vertices adjacent to visited vertices. Fritsch (Inform Process Lett 168:1006096, 2021) showed that the competitive ratio of an online algorithm is at most three for any unicyclic graph. On the other hand, Brandt et al. (Theor Comput Sci 839:176–185, 2020) showed a lower bound of two on the competitive ratio for any unicyclic graph. In this paper, we showed the competitive ratio of an online algorithm is at most 5/2 for any unicyclic graph.

DOI： 10.1007/s10878-024-01192-0

researchmap

Other Link： https://link.springer.com/article/10.1007/s10878-024-01192-0/fulltext.html

Authorship：Lead author,　Last author   Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

DOI： 10.1016/j.tcs.2021.10.005

researchmap

Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

DOI： 10.1016/j.tcs.2019.10.046

researchmap

Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer International Publishing  

DOI： 10.1007/978-3-030-26176-4_29

researchmap

Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer International Publishing  

DOI： 10.1007/978-3-319-94776-1_10

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). This problem models the situation where a large frame is fragmented into k packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the k packets. Kesselman et al. introduced this problem and showed that its competitive ratio is unbounded even when k=2. They also introduced a restricted variant of k-FTM, called k-OFTM. They proposed an online algorithm and showed that its competitive ratio is at most (2kB)/([B/k])+k for any B≧k, where B is the size of the buffer. They also presented a lower bound of B/([2B/k])=Ω(k) for deterministic online algorithms when 2B≧k and k is a power of 2. In this paper, we improve upper and lower bounds on the competitive ratio of k-OFTM. Our main result is to improve an upper bound of O(k^2) by Kesselman et al. to (5B+[B/k]-4)/([B/2k])=O(k) for B≧2k, which matches their lower bound of Ω(k) asymptotically. We also present an improved lower bound of (2B)/([B/(k-1)])+1 on the competitive ratio of deterministic online algorithms for any k≧2 and any B≧k-1, and the first nontrivial lower bound of k-1 on the competitive ratio of randomized algorithms for any k≧3 and any B.

CiNii Research

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

The problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee is formulated as the online buffer management problem. For this problem, several models are considered. We consider one of the models, called the k-frame throughput maximization problem (k-FTM for short) where k is an integer which is at least 2. This problem focuses on reconstructing frames from packets arriving at a FIFO buffer in a switch. Each frame consists of k packets. If all packets in a frame are transmitted, the frame can be reconstructed by a receiver. Since the size of the buffer is bounded, some arriving packets must be dropped if it is full. Our goal is to maximize the number of reconstructed frames. Kesselman et al. showed this problem has an unbounded competitive ration even when k=2. Hence, they considered an "order-respecting" input for k-FTM. They showed a 2kB/⌊B/k⌋+k-competitive deterministic algorithm for any B≧k where B is the size of the buffer, and gave a lower bound of B/⌊2B/k⌋ for any B(≧k) and any k which is a power of 2. We analyze a greedy algorithm for k=2 and show that its competitive ratio is at most 3 for any B, improving the previous upper bound of 4B/⌊B/2⌋+2(≧10). Also, we show the competitive ratio of any deterministic algorithm is at least 3 for any B in k=2, which matches our upper bound.

CiNii Research

researchmap

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service guarantee. For this problem, a lot of models have been considered. Among others, we focus on multi-queue switches in QoS Networks proposed by Azar et alAzar et al introduced the relaxed model in order to achieve a good upper bound on the competitive ratio for this model. In this paper, we improve the competitive ratios of several multi-queue models by improving an upper bound for the relaxed model. We propose an online algorithm DS (Dual Scheduling) for the relaxed model. This algorithm works for (either preemptive or non-preemptive) 2-value model, but it uses as subroutines online algorithms for the non-preemptive unit-value model, which has been extensively studied. The performance of DS depends on the performance of the algorithms used as subroutines. The followings are a couple of examples of the improvement on the competitive ratios of multi-queue models using our result: (i) We improved the competitive ratio of deterministic algorithms for the non-preemptive 2-value model from 4 to 3.177 for large enough B. a switch can store up to B packets simultaneously. (ii) We proved that the competitive ratio of randomized algorithms for the non-preemptive 2-value model is at most (17)/2-√<30>&sime;3.023 for large enough B.

CiNii Research

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Research

researchmap

Other Link： http://hdl.handle.net/2433/58224

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

The buffer management problem is a kind of online problems, which formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered, and in this paper, we focus on the model of shared memory switches. We improve the competitive ratio of the Longest Queue Policy (LQD) to 2-1/N, where N is the number of output ports in a switch.

CiNii Research

researchmap