142 citations · 287 across the 18 of their papers we have counts for
21 papers
Marriage and Roommate
Kazuo Iwama, Shuichi Miyazaki
This paper has two objectives. One is to give a linear time algorithm that solves the stable roommates problem (i.e., obtains one stable matching) using the stable marriage problem…
Improving the Bounds of the Online Dynamic Power Management Problem
Ya-Chun Liang, Kazuo Iwama, Chung-Shou Liao
We investigate the {\em power-down mechanism} which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle…
Tight Competitive Analyses of Online Car-sharing Problems
Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen +1
The car-sharing problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and total cars. Each request whi…
Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms
Kazuo Iwama, Junichi Teruyama, Shuntaro Tsuyama
The problem called "String reconstruction from substrings" is a mathematical model of sequencing by hybridization that plays an important role in DNA sequencing. In this problem, w…
Improved Average Complexity for Comparison-Based Sorting
Kazuo Iwama, Junichi Teruyama
This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is . For many ef…
Stable Nash Equilibria in the Gale-Shapley Matching Game
Sushmita Gupta, Kazuo Iwama, Shuichi Miyazaki
In this article we study the stable marriage game induced by the men-proposing Gale-Shapley algorithm. Our setting is standard: all the lists are complete and the matching mechanis…