30th International Workshop on Combinatorial Algorithms (IWOCA 2019), Best Paper Award,An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number小林靖明 小林佑輔 宮崎修一 玉置卓
2009年11月
電子情報通信学会, ISSソサイエティ活動功労賞宮崎修一
2007年5月
電子情報通信学会, 猪瀬賞(年間最優秀論文賞),A (2-c log N/N)-Approximation Algorithm for the Stable Marriage Problem岩間一雄 宮崎修一 岡本和也
International Journal of Foundations of Computer Science 34(07) 853-873 2023年6月 [査読有り]
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. The idea is that a stable matching of a roommate instance [Formul...
Discrete Mathematics, Algorithms and Applications 13(06) 2021年12月 [査読有り]
In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper,...
Given the same amount of hardware resource and bandwidth limitation, networks with optimal configurations enable Internet service providers to provide a lower end-to-end latency service for clients to use. In the case of designing VLAN, due to the...
Proceedings - 2008 International Symposium on Applications and the Internet (SAINT 2008) 2008年
We propose an extension of the attribute exchange between an Identity Provider (IdP) and an Service Provider (SP) in Shibboleth. While in the conventional framework of Shibboleth attributes are exchanged in immediate values, in our new extension a...
ALGORITHMS AND COMPUTATION (ISAAC 2008) 2008年 SPRINGER-VERLAG BERLIN
Online OVSF code assignment has an important application to wireless communications. Recently, this problem was formally modeled as an online problem, and performances of online algorithms have been analyzed by the competitive analysis. The previo...
INTERNATIONAL CONFERENCE ON INFORMATICS EDUCATION AND RESEARCH FOR KNOWLEDGE-CIRCULATING SOCIETY, PROCEEDINGS 2008年 IEEE COMPUTER SOC
The stable marriage problem is to find a matching between men and women, considering preference lists in. which. each person expresses his/her preference over the members of the opposite gender. The output matching must be stable, which, intuitive...
COMPUTERS AND GAMES (CG 2006) 2007年 SPRINGER-VERLAG BERLIN
We consider playing online games on peer-to-peer networks, without assuming servers that control the execution of a game. In such an environment, players may cheat the opponent by, for example, illegally replacing the cards in their hands. The aim...
THEORY AND PRACTICE OF COMPUTER SCIENCE (SOFSEM 2007), PROCEEDINGS 2007年 SPRINGER-VERLAG BERLIN
In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go ...