BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Koji M. Kobayashi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for the online interval coloring problem. In this paper, for online unit interval coloring, we show that the number of colors used by the Kierstead-Trotter algorithm is at most $3 ω(G) - 3$, where $ω(G)$ is the size of the maximum clique in a given graph $G$, and it is the best possible.
The online unit clustering problem was proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as follows: "Points" are given online in the $d$-dimensional Euclidean space one by one. An algorithm creates a "cluster," which is a $d$-dimensional rectangle. The initial length of each edge of a cluster is 0. An algorithm can extend an edge until it reaches unit length independently of other dimensions. The task of an algorithm is to cover a new given point either by creating a new cluster and assigning it to the point, or by extending edges of an existing cluster created in past times. The goal is to minimize the total number of created clusters. Chan and Zarrabi-Zadeh proposed some method to obtain a competitive algorithm for the $d$-dimensional case using an algorithm for the one-dimensional case, and thus the one-dimensional case has been extensively studied including some variants of the unit clustering problem. In this paper, we show a lower bound of $13/8 = 1.625$ on the competitive ratio of any deterministic online algorithm for the one-dimensional unit clustering, improving the previous lower bound $8/5 (=1.6)$ presented by Epstein and van Stee (WAOA2007 and ACM Transactions on Algorithms 7(1), 2010). Note that Ehmsen and Larsen (SWAT2010 and Theoretical Computer Science, 500, 2013) showed the current best upper bound of $5/3$, and conjectured that the exact competitive ratio in the one-dimensional case may be $13/8$.
Recently, the problems of evaluating performances of switches and routers have been formulated as online problems, and a great amount of results have been presented. In this paper, we focus on managing outgoing packets (called {\em egress traffic}) on switches that support Quality of Service (QoS), and analyze the performance of one of the most fundamental scheduling policies {\em Priority Queuing} ($PQ$) using competitive analysis. We formulate the problem of managing egress queues as follows: An output interface is equipped with $m$ queues, each of which has a buffer of size $B$. The size of a packet is unit, and each buffer can store up to $B$ packets simultaneously. Each packet is associated with one of $m$ priority values $α_{j}$ ($1 \leq j \leq m$), where $α_{1} \leq α_{2} \leq \cdots \leq α_{m}$, $α_{1} = 1$, and $α_{m} = α$ and the task of an online algorithm is to select one of $m$ queues at each scheduling step. The purpose of this problem is to maximize the sum of the values of the scheduled packets. For any $B$ and any $m$, we show that the competitive ratio of $PQ$ is exactly $2 - \min_{x \in [1, m-1] } \{ \frac{ α_{x+1} }{ \sum_{j = 1}^{x+1} α_{j} } \}$. That is, we conduct a complete analysis of the performance of $PQ$ using worst case analysis. Moreover, we show that no deterministic online algorithm can have a competitive ratio smaller than $1 + \frac{ α^3 + α^2 + α}{ α^4 + 4 α^3 + 3 α^2 + 4 α+ 1 }$.
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 an "order-respecting" variant of $k$-FTM, called $k$-OFTM, where inputs are restricted in some natural way. They proposed an online algorithm and showed that its competitive ratio is at most $\frac{2kB}{\lfloor B/k \rfloor} + k$ for any $B \ge k$, where $B$ is the size of the buffer. They also gave a lower bound of $\frac{B}{\lfloor 2B/k \rfloor}$ for deterministic online algorithms when $2B \geq 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 $\frac{5B + \lfloor B/k \rfloor - 4}{\lfloor B/2k \rfloor} = O(k)$ for $B\geq 2k$. Note that this upper bound is tight up to a multiplicative constant factor since the lower bound given by Kesselman et al.\ is $Ω(k)$. We also give two lower bounds. First we give a lower bound of $\frac{2B}{\lfloor {B/(k-1)} \rfloor} + 1$ on the competitive ratio of deterministic online algorithms for any $k \geq 2$ and any $B \geq k-1$, which improves the previous lower bound of $\frac{B}{\lfloor 2B/k \rfloor}$ by a factor of almost four. Next, we present the first nontrivial lower bound on the competitive ratio of randomized algorithms. Specifically, we give a lower bound of $k-1$ against an oblivious adversary for any $k \geq 3$ and any $B$.