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...
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), August 24-26, 2015, Princeton, NJ, USA 2015年 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear ...
ALGORITHMS AND COMPLEXITY (CIAC 2015) 2015年 SPRINGER-VERLAG BERLIN
This paper considers two variants of Multiple Knapsack Problems. The first one is the Multiple Knapsack Problem with Assignment Restrictions and Capacity Constraints (MK-AR-CC). In the MK-AR-CC(k) (where k is a positive integer), a subset of knaps...
Proceedings - 11th IEEE/IPSJ International Symposium on Applications and the Internet (SAINT 2011) 2011年
In this paper, we propose an online document delivery system which enables the sender to claim that documents are certainly delivered to the receiver. It is not difficult to realize this property by using a Trusted Third Party (TTP), but we focus ...
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2011) 2011年 SPRINGER-VERLAG BERLIN
Manlove and O'Malley [9] proposed the Student-Project Allocation Problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algo...
大学本部
情報科学研究科