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,...
オンライン問題の一つにk-Canadian Traveller Problem (k-CTP)がある.k-CTPとは,枝に重みの付いたグラフG=(V,E)上の与えられた頂点sからtまでの最短経路問題である.オンラインアルゴリズムは前もってグラフの構造と全ての枝のコストを知っている.しかし,グラフ上で高々κ個の枝が封鎖されており,枝が封鎖されているか否かはその枝に隣接する頂点に辿り着いた時に初めて分かる.Westphalは任意のグラフに対して,競合比が2k+1になることを示した.本稿では,枝...
Combinatorial Optimization and Applications (COCOA 2020) Lecture Notes in Computer Science book series (LNCS, volume 12577) 2020年12月 Springer International Publishing
大学本部
情報科学研究科