7 citations · 17 across the 16 of their papers we have counts for
7 papers · 1 filter
An optimal algorithm for 2-bounded delay buffer management with lookahead
Koji M. Kobayashi
The bounded delay buffer management problem, which was proposed by Kesselman et~al.\ (STOC 2001 and SIAM Journal on Computing 33(3), 2004), is an online problem focusing on buffer…
Online interval scheduling to maximize total satisfaction
Koji M. Kobayashi
The interval scheduling problem is one variant of the scheduling problem. In this paper, we propose a novel variant of the interval scheduling problem, whose definition is as follo…
Improved Bounds for Online Dominating Sets of Trees
Koji M. Kobayashi
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…
A tight analysis of Kierstead-Trotter algorithm for online unit interval coloring
Tetsuya Araki, Koji M. Kobayashi
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 onli…
An improved lower bound for one-dimensional online unit clustering
Jun Kawahara, Koji M. Kobayashi
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 on…
Better Bounds for Online -Frame Throughput Maximization in Network Switches
Jun Kawahara, Koji M. Kobayashi, Shuichi Miyazaki
We consider a variant of the online buffer management problem in network switches, called the -frame throughput maximization problem (-FTM). This problem models the situation…