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...
Koki Hamada   Kazuo Iwama   Shuichi Miyazaki   
ALGORITHMS (ESA 2011) 2011年 SPRINGER-VERLAG BERLIN
The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In its instance, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides. It is well-known that in any instance, there ...
THEORETICAL COMPUTER SCIENCE (IFIP TCS 2010) 2010年 SPRINGER-VERLAG BERLIN
In the seat reservation problem, there are k stations, si through s(k), and one train with n seats departing from the station Si and arriving at the station s(k). Each passenger orders a ticket from station s(i) to station s(j) (1 <= i < j &...
ALGORITHMS (ESA 2010), PT II 2010年 SPRINGER-VERLAG BERLIN
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (> 1.1379) unless P=NP, and the current best approximat...
2009 9th Annual International Symposium on Applications and the Internet (SAINT 2009) 2009年 IEEE
In this paper we design a certified e-mail exchange system based on a simultaneous secret exchange protocol. Among others, we use the protocol proposed by Okamoto and Ohta since the number of rounds it requires is relatively small compared to othe...
Koji Kobayashi   Shuichi Miyazaki   Yasuo Okabe   
PROCEEDINGS OF THE TWENTY-FIRST ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA 2009) 2009年 ASSOC COMPUTING MACHINERY
The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. We focus on multi-queue switches in QoS networks proposed by Azar et al. To achieve good upper bound...