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岩間一雄 宮崎修一 岡本和也
Discrete Mathematics, Algorithms and Applications 16(05) 2350057-1-2350057-39 2024年7月 [査読有り]
In the online facility assignment problem [Formula: see text], there exist [Formula: see text] servers [Formula: see text] on a metric space where each [Formula: see text] has an integer capacity [Formula: see text] and a request arrives one-by-on...
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...
Koji Kobayashi   Shuichi Miyazaki   Yasuo Okabe   
PROCEEDINGS OF THE NINETEENTH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA 2007) 2007年 ASSOC COMPUTING MACHINERY
The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered. In this paper, we focus on shared memory switches ...
PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2007) 2007年 SIAM
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is known to be APX-hard, and the current best known approximation algorithm achieves the ap...
ALGORITHMS AND DATA STRUCTURES (WADS 2007), PROCEEDINGS 2007年 SPRINGER-VERLAG BERLIN
The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this al...
K Iwama   S Miyazaki   K Okamoto   
ALGORITHM THEORY (SWAT 2004) 2004年 SPRINGER-VERLAG BERLIN
We propose an approximation algorithm for the problem of finding a maximum stable matching when both ties and unacceptable partners are allowed in preference lists. Our algorithm achieves the approximation ratio 2 - c (N)-(log N) for an arbitraril...